3 Sum

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

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        
    }
}

This problem's solutions can be classified into two kinds, the first is to sort the nums first , the second is to go without sorting.

the first kind

In order to make sure that all 3 numbers are different from each other(which is also the key part of this problem),

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> lst = new ArrayList<>();
        Arrays.sort(nums);
        for(int i = 0; i < nums.length-2; i++) {
            //avoid the duplicate first number, if duplicate, increase i
            if(i == 0 || (i>0 && nums[i] != nums[i-1])) {
                int lo = i+1, hi = nums.length-1, sum = 0-nums[i];
                while(lo < hi) {
                    if(nums[lo]+nums[hi] == sum) {
                        lst.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                        while(lo < hi && nums[lo] == nums[lo+1]) lo++;
                        while(hi > lo && nums[hi] == nums[hi-1]) hi--;
                        lo++; hi--;
                    }
                    else if(nums[lo]+nums[hi] < sum) {
                        lo++;
                    }else {
                        hi--;
                    }
                }
            }
        }
        return lst;
            
    }
}

similar problems

• 3 sum smaller

  ---

  Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

  Example:

  Input: nums = [-2,0,1,3], and target = 2
  Output: 2 
  Explanation: Because there are two triplets which sums are less than 2:
               [-2,0,1]
               [-2,0,3]
  
  

  Follow up: Could you solve it in O(n2) runtime?

Thoughts: it does not require the index's output, so it can still use the sorting method.

find the number of index triplets i, j, k with 0 <= i < j < k < n

means that it requires 3 different numbers, but not necessarily digitally different from each other, but they need to be different identity. So there is no need to remove the duplicate ones. And there is also a very quick way to calculate the possible solutions while fixing the second number and 3rd number.

class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int res = 0;
        for(int i = 0; i < nums.length-2; i++) {
            int lo = i+1, hi = nums.length-1, sum = target-nums[i];
            while(lo < hi) {
                if(nums[lo] +nums[hi] < sum) {
                    res+= hi -lo;
                    lo++;
                }else {
                    hi--;
                }
            }
        }
        return res;
    }
}

• 3sum closest

  ---

  Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

  Example:

  Given array nums = [-1, 2, 1, -4], and target = 1.
  
  The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
  

Thoughts:

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int diff = target-nums[0]-nums[1]-nums[2];
        for(int i = 0; i<nums.length-2; i++) {
            int lo = i+1, hi = nums.length-1;
            
            //System.out.println("0");
            //System.out.println(lo+" "+hi+" "+diff);
            while( lo < hi && diff != 0) {
                //System.out.println("0.2");
                if(Math.abs(target - nums[i]-nums[lo]-nums[hi]) < Math.abs(diff)) {
                    //System.out.println("0.5");
                    diff = target-nums[i]-nums[lo]-nums[hi]; 
                }
                if(nums[i]+nums[lo]+nums[hi] < target) {
                    while(lo<hi && nums[lo]==nums[lo+1]) lo++;
                    //System.out.println("1");
                    lo++;
                } else{
                   while(lo<hi && nums[hi]==nums[hi-1]) hi--;
                    //System.out.println("2");
                    hi--;
                }
            }
                
            }
        //System.out.println("5");
        return target-diff;
    }
}