[lint]. 2 Sum II.java

M
1516439472
tags: Array, Two Pointers, Binary Search, Lint

与 2sum II - input array is sorted类似. 都是sort array, 然后two pointer.

LintCode的题. 注意找的是greater/bigger than target。

由于给定条件允许O(nLogn):   
   sort
   two pointer

while里面two pointer移动。每次如果num[left]+num[right] > target，那么其中所有num[left++]的加上num[right]都>target.   
也就是,num[right]不动，计算加入挪动left能有多少组，那就是: right-left这么多。 全部加到count上去。     
然后right--.换个right去和前面的left部分作比较。

```
/*
Given an array of integers, find how many pairs in the array such that 
their sum is bigger than a specific target number. Please return the number of pairs.
Example
numbers=[2, 7, 11, 15], target=24

return 1

Challenge
Either of the following solutions are acceptable:

O(1) Space, O(nlogn) Time
Tags Expand 
Two Pointers

*/

/*
Thoughts:
After doing Trigle Count...Can we just do the same for this, move while pointers to center?
OMG. The original idea was sooooooo complicated.
*/
public class Solution {
    public int twoSum2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 0;
        int left = 0;
        int right = nums.length - 1;
        Arrays.sort(nums);
        while (left < right) {
            if (nums[left] + nums[right] > target) {
                count += (right - left);
                right--;
            } else {
                left++;
            }
        }
        return count;
    }
}

//Below are bad solutions. Don't worry about them

/*

Thoughts:
1. For loop to try each element from (i ~ end). O(n)
2. In for, do binary search on nums[i] + nums[j] > target, 
3. count += (length - j)

Note: when not found, return nums.length, because at then end, (length - length) == 0, which will be added to count.
Note: Always pin target down, and move mid to compare. Don't get confused
Also, take care of corner cases.
*/

public class Solution {
    public int twoSum2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 0;
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            int index = binarySearch(nums, target - nums[i - 1], i, nums.length - 1);
            count += nums.length - index;
        }
        return count;
    }

    public int binarySearch(int[] nums, int target, int start, int end) {
        int mid;
        int sum;
        while (start + 1 < end) {
            mid = start + (end - start) /2;
            if (mid - 1 >= 0 && nums[mid-1] <= target && target < nums[mid]) {
                return mid;
            } else if (mid + 1 < nums.length &&  nums[mid] <= target && target < nums[mid + 1]) {
                return mid + 1;
            } else if (target < nums[mid]) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (nums[start] > target) {
            return start;
        }
        return (nums[end] > target) ? end : nums.length;
    }
}

//Brutle force, O(n^2)
public class Solution {
    public int twoSum2(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                count += (nums[i] + nums[j] > target) ? 1 : 0;
            }
        }
    }
}

```