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.

  1. For example, given array S = [-1, 0, 1, 2, -1, -4],
  3. A solution set is:
  4. [
  5.   [-1, 0, 1],
  6.   [-1, -1, 2]
  7. ]

Solution:

  1. public class Solution {
  3.   public List<List<Integer>> threeSum(int[] num) {
  4.     List<List<Integer>> res = new ArrayList<List<Integer>>();
  6.     Set<String> set = new HashSet<String>();
  8.     Arrays.sort(num);
  10.     int n = num.length;
  12.     for (int i = 0; i < n - 2; i++) {
  13.       int j = i + 1, k = n - 1;
  15.       while (j < k) {
  16.         int sum = num[i] + num[j] + num[k];
  18.         if (sum == 0) {
  19.           String key = String.format("%d,%d,%d", num[i], num[j], num[k]);
  21.           if (!set.contains(key)) {
  22.             set.add(key);
  24.             List<Integer> sol = new ArrayList<Integer>();
  25.             sol.add(num[i]);
  26.             sol.add(num[j]);
  27.             sol.add(num[k]);
  29.             res.add(sol);
  30.           }
  32.           j++;
  33.           k--;
  34.         } else if (sum < 0) {
  35.           j++;
  36.         } else {
  37.           k--;
  38.         }
  39.       }
  40.     }
  42.     return res;
  43.   }
  45. }

Time complexity: O(n^2)