Two Sum II

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

Given numbers =[2, 7, 11, 15], target =24. Return1. (11 + 15 is the only pair)

public int twoSum2(int[] nums, int target) {
    if(nums == null || nums.length == 0) {
        return 0;
    }
    Arrays.sort(nums);
    int res = 0;
    int left = 0, right = nums.length - 1;
    while(left < right) {
        int sum = nums[left] + nums[right];
        if(sum > target) {
            res += right - left;
            right--;
        }
        else {
            left++;
        }
    }
    return res;
}

Follow up:

Triangle Count

Given an array of integers, how many three numbers can be found in the array, so that we can build an triangle whose three edges length is the three numbers that we find?

Example

Given array S =[3,4,6,7], return3. They are:

[3,4,6]
[3,6,7]
[4,6,7]

Given array S =[4,4,4,4], return4. They are:

[4(1),4(2),4(3)]
[4(1),4(2),4(4)]
[4(1),4(3),4(4)]
[4(2),4(3),4(4)]

public int triangleCount(int S[]) {
    if(S == null || S.length == 0) {
        return 0;
    }
    Arrays.sort(S);
    int res = 0;
    for(int i = 0; i < S.length; i++) {
        int target = S[i];
        int left = 0, right = i - 1;
        while(left < right) {
            if(S[right] + S[left] > target) {
                res += right - left;
                right--;
            }
            else {
                left++;
            }
        }
    }
    return res;
}