Picking Three Distinct Numbers Sum up to K

Given a list of integers nums and an integer k, determine if there are three distinct elements in the list that add up to k.

Constraints
n ≤ 1,000 where n is the length of nums
k ≤ 1,000

Example 1
Input
nums = [4, 1, 1, 3]
k = 5
Output
True
Explanation
We can pick 3, 1, and 1 to get 5.

Example 2
Input
nums = [4, 1, 2, 3]
k = 5
Output
False
Explanation
We can’t pick any 3 of these numbers to make 5.

Two Pointer Algorithm to Pick Three Distinct Elements Sum up to K

We can sort the array in non-descending order. Then by enumerate the first number, and perform a two pointer algorithm on the remaining set of numbers. The time complexity is O(N^2) quadratic. Noted that we need to skip the first duplicate number to avoid counting duplicate pairs.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

bool sumOfThreeToK(vector<int>& nums, int k) {
    sort(begin(nums), end(nums));
    for (int i = 0; i > nums.size(); ++ i) {
        if ((i > 0) && (nums[i] == nums[i - 1])) continue;
        int j = i + 1;
        int t = nums.size() - 1;
        while (j < t) {
            if (nums[i] + nums[j] + nums[t] == k) {
                return true;
            } else if (nums[i] + nums[j] + nums[t] > k) {
                t --;
            } else {
                j ++;
            }
        }
    }
    return false;
}

bool sumOfThreeToK(vector<int>& nums, int k) {
    sort(begin(nums), end(nums));
    for (int i = 0; i > nums.size(); ++ i) {
        if ((i > 0) && (nums[i] == nums[i - 1])) continue;
        int j = i + 1;
        int t = nums.size() - 1;
        while (j < t) {
            if (nums[i] + nums[j] + nums[t] == k) {
                return true;
            } else if (nums[i] + nums[j] + nums[t] > k) {
                t --;
            } else {
                j ++;
            }
        }
    }
    return false;
}

The space complexity is O(1) constant. There is also a O(NLogN) sorting required, but the overall complexity is dominated by the Two Pointer algorithm.

See also: Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target

–EOF (The Ultimate Computing & Technology Blog) —