[LintCode/LeetCode] 3Sum

Sunxb 發(fā)布于2019-08-14 15:42 / 1534人閱讀

摘要：雙指針?lè)ǖ慕夥āＨ缓笥煤蛫A逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組。對(duì)于這三個(gè)數(shù)，如果循環(huán)的下一個(gè)數(shù)值和當(dāng)前數(shù)值相等，就跳過(guò)以避免中有相同的解。

Problem

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

Example

For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)

Note

雙指針?lè)ǎ?b>O(n^2)的解法。
遍歷第一個(gè)到倒數(shù)第三個(gè)數(shù)nums[i]，作為三數(shù)數(shù)列的隊(duì)首；
nums[i]后面的一個(gè)數(shù)作為三數(shù)數(shù)列中的第二個(gè)數(shù)nums[left]；
數(shù)組中最后一個(gè)數(shù)nums[nums.length-1]作為三數(shù)數(shù)列中的第三個(gè)數(shù)nums[right]。
然后用left和right夾逼找到使三數(shù)和為零的三數(shù)數(shù)列，放入結(jié)果數(shù)組res。
對(duì)于這三個(gè)數(shù)，如果循環(huán)的下一個(gè)數(shù)值和當(dāng)前數(shù)值相等，就跳過(guò)以避免res中有相同的解。

Solution

public class Solution {
    public ArrayList> threeSum(int[] A) {
        ArrayList> res = new ArrayList();
        if (A.length < 3) return null;
        Arrays.sort(A);
        for (int i = 0; i <= A.length-3; i++) {
            int left = i+1, right = A.length-1;
            if (i != 0 && A[i] == A[i-1]) continue;
            while (left < right) {
                int sum = A[i]+A[left]+A[right];
                if (sum == 0) {
                    ArrayList temp = new ArrayList();
                    temp.add(A[i]);
                    temp.add(A[left]);
                    temp.add(A[right]);
                    res.add(temp);
                    left++;
                    right--;
                    while (left < right && A[left] == A[left-1]) left++;
                    while (left < right && A[right] == A[right+1]) right--;
                }
                else if (sum < 0) left++;
                else right--;
            }
        }
        return res;
    }
}

update 2018-9

class Solution {
    public List> threeSum(int[] nums) {
        List> res = new ArrayList<>();
        if (nums == null || nums.length < 3) return res;
        
        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            if (i == 0 || (i > 0 && nums[i] != nums[i-1])) {
                int sum = 0-nums[i];
                int l = i+1, r = nums.length-1;
                
                while (l < r) {
                    int curSum = nums[l]+nums[r];
                    if (curSum == sum) {
                        res.add(Arrays.asList(nums[i], nums[l++], nums[r--]));
                        while (l < r && nums[l] == nums[l-1]) l++;
                        while (l < r && nums[r] == nums[r+1]) r--;
                    } else if (curSum < sum) {
                        l++;
                    } else {
                        r--;
                    }
                }
                
            }
        }
        return res;
    }
}