15. 3Sum.md

15. 3Sum

---

leetcode Daily Challenge on July 8th, 2020.

---

Difficulty : Medium

Related Topics : Array、Two Pointers

---

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

---

Solution

• java

  • mine

    • Runtime: 377 ms, faster than 15.52%, Memory Usage: 55.5 MB, less than 5.29% of Java online submissions

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < nums.length - 2; i++) {
            int t = i + 1, end = nums.length - 1;
            while (t < end) {
                int num = nums[i] + nums[t] + nums[end];
                if (num == 0) {
                    String builder = new StringBuilder()
                            .append(nums[i]).append(",")
                            .append(nums[t]).append(",")
                            .append(nums[end])
                            .toString();
                    hashSet.add(builder);
                    t++;
                } else if (num < 0) {
                    t++;
                } else {
                    end--;
                }
            }
        }
        for (String s : hashSet) {
            String[] splits = s.split(",");
            List<Integer> t = new ArrayList<>();
            for (String split : splits) {
                t.add(Integer.parseInt(split));
            }
            res.add(t);
        }
        return res;
    }
    

    • got from the most votes Runtime: 19 ms, faster than 74.89%, Memory Usage: 43.6 MB, less than 100.00% of Java online submissions

    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        for(int i = 0; i < len - 2; i++){
            if(i != 0 && nums[i] == nums[i - 1]){
                continue;
            }
            if(nums[i] > 0){
                break;
            }
            int s = i + 1, e = len - 1;
            while(s < e){
                int t = nums[i] + nums[s] + nums[e];
                if (t == 0) {
                    res.add(Arrays.asList(nums[i], nums[s], nums[e]));
                    while (s < e && nums[s] == nums[s + 1]) {
                        s++;
                    }
                    while (s < e && nums[e] == nums[e - 1]) {
                        e--;
                    }
                    s++;
                    e--;
                }else if(t > 0){
                    e--;
                }else{
                    s++;   
                }
            }
        }
        return res;
    }
    

---

• the most votes

  Runtime: 28 ms, faster than 90.58%, Memory Usage: 47.8 MB, less than 85.86% of Java online submissions

  public List<List<Integer>> threeSum(int[] num) {
      Arrays.sort(num);
      List<List<Integer>> res = new LinkedList<>();
      for (int i = 0; i < num.length - 2; i++) {
          if (i == 0 || num[i] != num[i - 1]) {
              int lo = i + 1, hi = num.length - 1, sum = 0 - num[i];
              while (lo < hi) {
                  if (num[lo] + num[hi] == sum) {
                      res.add(Arrays.asList(num[i], num[lo], num[hi]));
                      while (lo < hi && num[lo] == num[lo + 1]) {
                          lo++;
                      }
                      while (lo < hi && num[hi] == num[hi - 1]) {
                          hi--;
                      }
                      lo++;
                      hi--;
                  } else if (num[lo] + num[hi] < sum) {
                      lo++;
                  } else {
                      hi--;
                  }
              }
          }
      }
      return res;
  }
  

---