Question

Formatted question description: https://leetcode.ca/all/15.html

15 -	3 Sum

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.

Note:
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.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

@tag-array

Algorithm

Sort the original array, and then start traversing the sorted array.

Note that the traversal is not to the last stop, but to the third from the bottom. Here we can do a pruning optimization first, that is, break when traversing to a positive number, Because the array is now ordered, if the first number to be fixed is a positive number, then the following numbers if they are all positive numbers, the sum will never be zero.

Then add the process of skipping if repeated. The processing method is to start with the second number. If it is equal to the previous number, skip it because you don’t want to fix the same number twice.

For the traversed number, subtract the fix number from 0 to get a target, and then only need to find the sum of the two numbers is equal to the target. Use two pointers to point to the first and last two numbers of the array starting after the fix number.

If the sum of the two numbers happens to be the target, then the two numbers and the fix number are stored in the result together. Then is to skip the step of repeating numbers. Both pointers need to detect repeated numbers.
If the sum of the two numbers is less than the target, move the pointer i on the left one bit to the right to increase the number pointed to.
In the same way, if the sum of the two numbers is greater than the target, move the pointer j on the right to the left to reduce the number pointed to

Code

Java

public class Three_Sum {
	public static void main(String[] args) {
	    List<List<Integer>> list = new ArrayList<>();
	    int[] a = new int[]{3,2,1};

	    Arrays.sort(a);
	    System.out.println(a[0]);
	}

    // time: O(N)
    // space: O(1)
	public class Solution {

	    List<List<Integer>> list = new ArrayList<>();

	    public List<List<Integer>> threeSum(int[] nums) {

	        if(nums.length < 3) {
	            return list;
	        }

	        Arrays.sort(nums);

	        // hold one pointer, other two pointer moving
	        for(int ancher = 0; ancher < nums.length; ancher++) {

	            if(ancher > 0 && nums[ancher] == nums[ancher - 1]) {
	                continue;
                }

	            int i = ancher + 1;
	            int j = nums.length -1;

	            while(i < j) {

	                if(nums[ancher] + nums[i] + nums[j] == 0) {

	                    // @note: Arrays.asList()
	                    list.add(Arrays.asList(nums[ancher], nums[i], nums[j]));

	                    i++;
	                    j--;

	                    // @note: optimization. above i,j is updated already, compare with previous position
	                    while(i < j && nums[i] == nums[i - 1]) {
	                        i++;
	                    }
	                    while(j > i && nums[j] == nums[j + 1]) {
	                        j--;
	                    }

	                } else if(nums[ancher] + nums[i] + nums[j] < 0) {
	                    i++;

	                    // @note: same here, possibly updated already, note i-1 or i+1
	                    while(i < j && nums[i] == nums[i - 1]) {
	                        i++;
	                    }
	                } else {
	                    j--;

	                    // @note: same here, possibly updated already, note i-1 or i+1
	                    while(j > i && j + 1 < nums.length && nums[j] == nums[j + 1]) {
	                        j--;
	                    }
	                }
                }

	        }

	        return list;
	    }
	}

}

// OJ: https://leetcode.com/problems/3sum/
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& A) {
        sort(begin(A), end(A));
        vector<vector<int>> ans;
        int N = A.size();
        for (int i = 0; i < N - 2; ++i) {
            if (i && A[i] == A[i - 1]) continue;
            int L = i + 1, R = N - 1;
            while (L < R) {
                int sum = A[i] + A[L] + A[R];
                if (sum == 0) ans.push_back({ A[i], A[L], A[R] });
                if (sum >= 0) {
                    --R;
                    while (L < R && A[R] == A[R + 1]) --R;
                }
                if (sum <= 0) {
                    ++L;
                    while (L < R && A[L] == A[L - 1]) ++L;
                }
            }
        }
        return ans;
    }
};

class Solution(object):
  def threeSum(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """
    res = []
    nums.sort()
    for i in range(0, len(nums)):
      if i > 0 and nums[i] == nums[i - 1]:
        continue
      target = 0 - nums[i]
      start, end = i + 1, len(nums) - 1
      while start < end:
        if nums[start] + nums[end] > target:
          end -= 1
        elif nums[start] + nums[end] < target:
          start += 1
        else:
          res.append((nums[i], nums[start], nums[end]))
          end -= 1
          start += 1
          while start < end and nums[end] == nums[end + 1]:
            end -= 1
          while start < end and nums[start] == nums[start - 1]:
            start += 1
    return res

15 - 3Sum

Question

Algorithm

Code

All Problems

All Solutions