Find a pair in an array with a sum equal to the target using sorting

Problem statement

Given array nums of n numbers and another number target, determines whether or not there exist two elements in nums whose sum is exactly equal to target.

Problem statement taken from: https://www.geeksforgeeks.org/given-an-array-a-and-a-number-x-check-for-pair-in-a-with-sum-as-x/

Example 1:

Input: nums = {0, -1, 2, -3, 1}, target = -2
Output: [3,4]

Example 2:

Input: nums = {1, -2, 1, 0, 5}, target = 0
Output: []

Explanation

The problem can be solved in O(NlogN) time, without using extra space. The NlogN is the average time taken to sort an array.

Sorting and two pointers

Algorithm

- Sort the array in ascending order.
- Initialize two variables l and r.
  - Set l = 0 pointing to leftmost index of array.
  - Set r = n - 1 pointing to rightmost index of array.
- Loop while l < r
  - if (nums[l] + nums[r] == x) then return [l, r]
  - else if (nums[l] + nums[r] < x) then l++
  - else r--
- If no such pair found return []

C++ solution

class Solution {
public:
    vector<int> twoSum(vector<int>&nums, int target) {
        sort(nums.begin(), nums.end());

        int l = 0, r = nums.size() - 1;
        while(l < r){
            if (nums[l] + nums[r] == target){
                return vector<int> {l, r};
            } else if (nums[l] + nums[r] < target){
                l++;
            } else {
                r--;
            }
        }

        return vector<int> {};
    }
};

Golang solution

func twoSum(nums []int, target int) []int {
    sort.Ints(nums)
    l := 0
    r := len(nums) - 1

    for l < r {
        if nums[l] + nums[r] == target {
            return []int{l, r}
        } else if nums[l] + nums[r] < target {
            l++
        } else {
            r--
        }
    }

    return []int{}
}