3Sum

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]
]

解法一

public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> result = new ArrayList<>();
            for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
                if (i>0 && nums[i]==nums[i-1] ) continue;
                for (int j = i + 1; j < nums.length - 1 && nums[i] + nums[j] <= 0; j++) {
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                    //二分查找
                    int index = Arrays.binarySearch(nums, j + 1, nums.length, -(nums[i] + nums[j]));
//                    System.out.println("i:" + i + "\tj:" + j + "\tindex:" + index);
                    if (index > 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[index]);
                        result.add(list);
                    }
                }
            }
            return result;
}

解法二

 public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            //key:数组的元素
            //value:是排序后的索引 要是数组存在相同的元素，那么存最大的索引
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 2; i < nums.length; i++) {
                if (nums[i] >= 0){
                    map.put(nums[i], i);
                }
            }

            List<List<Integer>> result = new ArrayList<>();
            for (int i = 0; i < nums.length - 2 && nums[i] <= 0; i++) {
                if (i > 0 && nums[i] == nums[i - 1]) continue;
                for (int j = i + 1; j < nums.length - 1 && nums[i] + nums[j] <= 0; j++) {
       
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                    int key = -(nums[i] + nums[j]);
                    boolean b = map.containsKey(-(nums[i] + nums[j]));
                    //算法复杂度O(1)
                    Integer index = map.get(key);
                    if (b && index > j) {
                        result.add(Arrays.asList(nums[i], nums[j], key));
                    }
                }
            }
            return result;
        }