Algorithm 3Sum

Description

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:

[

[-1, 0, 1],

[-1, -1, 2]

]

Submission

package com.cctoken.algorithm;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @author chenchao
 */
public class ThreeSum {

  public static List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res = new LinkedList<List<Integer>>();
    if (nums.length < 3) {
      return res;
    }
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 2; ++i) {
      if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
      }
      int j = i + 1;
      int k = nums.length - 1;
      while (j < k) {
        if (nums[i] + nums[j] + nums[k] > 0) {
          k--;
        } else if (nums[i] + nums[j] + nums[k] < 0) {
          j++;
        } else {
          List<Integer> oneSolution = new LinkedList<Integer>();
          oneSolution.add(nums[i]);
          oneSolution.add(nums[j]);
          oneSolution.add(nums[k]);
          res.add(oneSolution);
          j ++;
          while (j < k) {
            if (nums[j] == nums[j - 1]) {
              j++;
            } else {
              break;
            }
          }
          k --;
          while (j < k) {
            if (nums[k] == nums[k + 1]) {
              k --;
            } else {
              break;
            }
          }
        }
      }
    }
    return res;
  }

  public static void main(String[] args) {
    int[] nums = new int[]{0, 0, 0, 0};
    List<List<Integer>> res = threeSum(nums);
    System.out.println(res.size());
  }
}

Solution

解题思路，首先将数组进行排序，然后从左至右一次选择一个固定位i，则只需在 i+1~length-1 这段 索引区域内找到两个值与 nums[i] 的和为0即可

为什么要先排序，因为如果不排序，采用穷举的方式需要的时间复杂度是O(n3)

采用内置的快排，时间复杂度为 O(NlogN),之后再采用遍历的方式，时间复杂度可以控制在O(N²)

关于 i > 0 && nums[i] == nums[i-1] 的判断，主要是为了避免出现相同的和序列，比如 -1,-1,0,1，在第一次遍历之后能得到 结果(-1,0,1),当i的位置为1时，指向的仍是-1,此时无需记录

同理 在内部循环， j<k && nums[j] == nums[j-1] 以及 j < k && nums[k]==nums[k+1] 实际上也是出于同样的目的。

采用这样的方式主要是为了避免出现重复的结果，之前采用的方式是在 res.add(oneSolution) 的时候判断下，当前res中是否存在相同的结果集，但是发现执行效率太低了，上面代码提供的方式更快，附上 submission 的 结果。

image.png