LeetCode Problem: Two Pointer Topics

1. 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).

To solve this problem, one possible way is to use DFS to generate all the 3-element subsets of the given input array(just like what we have done in the LeetCode problem Subsets):

import java.util.ArrayList;
import java.util.List;

public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }

        return dfs(nums, target, new ArrayList<Integer>(), 0);
    }

    public int dfs(int[] nums, int target, List<Integer> current, int index) {
        if (current.size() == 3) {
            return current.get(0) + current.get(1) + current.get(2);
        }

        int sum = nums[0] + nums[1] + nums[2];
        for (int i = index; i < nums.length; i++) {
            current.add(nums[i]);
            int newSum = dfs(nums, target, current, i + 1);
            sum = Math.abs(target - newSum) < Math.abs(target - sum) ? newSum : sum;
            current.remove(current.size() - 1);
        }

        return sum;
    }
}

However, this way cost would cost too much time(Time Limit Exceeded on LeetCode). A more efficient way is to use two pointers:

import java.util.Arrays;

public class ThreeSumClosest {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);

        int result = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length; i++) {

            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(target - sum) < Math.abs(target - result)) {
                    result = sum;
                }

                if (sum < target) {
                    left++;
                } else {
                    right--;
                }

            }

        }
        return result;
    }
}

The process of the above code is like this:https://www.youtube.com/watch?v=cJOkAOgfRr8

---