No.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: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]
]

思路与想法：

在吃中饭的空当写下第一个解题报告，算是一个开始，之后也要时时总结，应该会比题海战术更有效。

This problem is just a little bit different from the problem two sum, so we can also use two pointers to solve this problem since A+B+C = A+(B+C), but in this problem, there are two important points:

1. we need to traverse all the elements in the array, this is the first for loop, the important part is to skip duplicate elements.
2. in every element, we use two pointer method to find the target and move the left pointer and right pointer accordingly, the important part is after we find the correct solution, we still need to skip duplicates in case of corner case like {0,0,0,0,0,0}

Both two important points are because the solution cannot contain duplicate triplets.

2017.5.16

Solution:

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int target = nums[i];
            if (i > 0 && target == nums[i - 1]) {
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                if (nums[left] + nums[right] + target < 0) {
                    left++;
                } else if (nums[left] + nums[right] + target > 0) {
                    right--;
                } else if (nums[left] + nums[right] + target == 0) {
                    List<Integer> temp = new ArrayList<Integer>();
                    temp.add(target);
                    temp.add(nums[left]);
                    temp.add(nums[right]);
                    result.add(temp);

                    while (left + 1 < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    while (right - 1 > left && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    left++;
                    right--;
                }
            }
        }
        return result;
    }
}

Time Complexity:

O(n^2)