From Two Sum to Three Sum Cloest

There is a famous leetcode question, 2 Sum. And recently, there are lots of variants are asked in interviews.

There are a tricky method to answer 2 sum question, yes, HashSet. But when the question comes to ask you find the closest value. That method doesn't help. Instead, we need to use two pointers to solve the question.

So, Let's begin.
-----------------------------------------------------------------------------------------------------------------

The two sum question is: give you an integer array , and a target value. Ask you to find the pair whose sum is equal to the given target value.

   public int[] twoSum(int[] nums, int target) {
        // first, validate the input
        if (nums == null || nums.length == 0)
            throw new IllegalArgumentException("the input is not valid");

        int[] arraycopy = new int[];
        for(int i = 0; i< nums.length; i++) {
            arraycopy[i] = nums[i];
        }

        Arrays.sort(arraycopy);
        int index1 = -1, index2 = -1;
        // low pointer in the left, high pointer in the right
        int low = 0, high = nums.length-1;
        while (low < high) {
            if (arraycopy[low] + arraycopy[high] == target){
                index1 = low;
                index2 = high;
                break;;
            } else if (arraycopy[low] + arraycopy[high] > target){
                high--;
            } else {
                low++;
            }
        }
        if (index1 == -1)  {
            // means there is no match value
            throw new exception(...);
        }

        boolean index1Find = false, index2Find = false;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == arraycopy[index1] && !index1Find){
                index1 = i;
                continue;
            }
            if (nums[i] == arraycopy[index2] && !index2Find){
                index2 = i;
                continue;
            }
        }
        result new int[]{index1, index2};
    }

Time complexity O(logn) because of array sorting.
--------------------------------------------------------------------------------

Similarly, we can use this method to answer three sum question. The only thing needs to be careful is avoiding duplicates.

    public List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 3) return result;

        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            int low = i + 1, high = nums.length-1, target = -nums[i];
            while (low < high) {
                if (nums[low] + nums[high] == target){
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[low]);
                    list.add(nums[high]);
                    result.add(list);
                    low++, high--;
                    while (low < high && nums[low] == nums[low-1])  // to avoid duplicates
                        low++;
                    while (low < high && nums[high] == nums[high+1])
                        high--;
                } else if (nums[low] + nums[high] > target){
                    high--;
                } else {
                    low++;
                }
            }
        }
        return result;
    }



--------------------------------------------------------------------------------
Let's move to the question 3 sum smaller