[LintCode][Two Pointers] Two Sum

Problem

More Discussions

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. Return 1. (11 + 15 is the only pair)

Challenge

Do it in O(1) extra space and O(nlogn) time.

Solution

Two Pointers的思想，先排序数组。如果a[i] + a[j] > target, 说明 a[i..j]之间的数的和都大于target所以只要累加j-i个数就行了，之后j--，继续寻找。

class Solution {
public:
    /**
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    int twoSum2(vector<int> &nums, int target) {
        // Write your code here
        sort(nums.begin(), nums.end());
        int i = 0;
        int j = nums.size() - 1;
        int count = 0;
        while (i < j) {
            int sum = nums[i] + nums[j];
            if (sum > target) {
                count += j - i;
                j--;
            } else {
                i++;
            }
        }
        
        return count;
    }
};