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

Sliding Window Maximum

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the knumbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7

Therefore, return the max sliding window as [3,3,5,5,6,7].

-----------------------------------------------------------------------------------------------------------------------

There are mainly two methods to solve this problem: PriorityQueue and Deque. Both two methods use O(k) space. But time complexity for PriorityQueue is O(nlogk) and O(n) for Deque.

Let's write the first method:

(1)  PriorityQueue

    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums == null || nums.length == 0) return new int[0];

        int[] res = new int[nums.length - k + 1];

        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < nums.length; i++) {

            if (i >= k) pq.remove(nums[i-k]);

            pq.offer(nums[i]);

            if (i>=k-1) res[i+1-k] = pq.peek();

        }

        return res;

    }

(2) Deque

    public int[] maxSlidingWindow(int[] nums, int k) {

        if(nums == null || nums.length == 0) return new int[0];

        LinkedList<Integer> deque = new LinkedList<Integer>();

        int[] res = new int[nums.length + 1 - k];

        for (int i = 0; i < nums.length; i++) {

           // i - k is the left most element index. So it need to be removed when the window sided over 

            if (!deque.isEmpty() && deque.peek() == i-k) deque.poll();

           // make sure the deque is always decreasing

            while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i])

                deque.removeLast();

            // add the element to the end

            deque.offer(i);

            if (i>=k-1) res[i+1-k] = nums[deque.peek()];

        }

        return res;

    }