Two Numbers with Sum S

1. Problem Description

Given an array sorted in increasing order and a number S, find two numbers in the array whose sum is exactly S. If there are multiple pairs whose sum equals S, output the pair with the smallest product.

2. Approach

• Two pointers: because the array is sorted, one pointer starts at the first element and moves right, while the other starts at the last element and moves left

3. Implementation

• java

public class 和为S的两个数字
{
    public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum)
    {
        ArrayList<Integer> res = new ArrayList<>();
        // Check parameters
        if (array == null || array.length == 0)
        {
            return res;
        }
        // One pointer points to the first element and the other to the last element; calculate their sum.
        int left = 0;
        int right = array.length - 1;
        while (left < right)
        {
            int currentSum = array[left] + array[right];
            if (currentSum == sum)
            {
                res.add(array[left]);
                res.add(array[right]);
                return res;
            }
            // If the sum is greater than sum, move the second pointer left.

            else if (currentSum > sum)
            {
                right--;
            }
            // If the sum is less than sum, move the first pointer right.
            else
            {
                left++;
            }

        }

        return res;
    }
}

• go

// Time complexity: O(n)
// Space complexity: O(1)
func FindNumbersWithSum(array []int, sum int) []int {
	if len(array) == 0 {
		return nil
	}

	left := 0
	right := len(array) - 1
	data := make([]int, 2)
	for left < right {
		currentSum := array[left] + array[right]
		if currentSum == sum {
			data[0] = array[left]
			data[1] = array[right]
			return data
		} else if currentSum < sum {
			left++
		} else {
			right--
		}
	}

	return nil
}

func twoSum(nums []int, target int) []int {
    left := 0
    right := len(nums)-1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == target {
            return []int{nums[left], nums[right]}
        } else if sum < target {
            left++
        } else {
            right--
        }
    }
    return []int{-1,-1}
}

4. References

• Two Numbers with Sum S - NowCoder
• Sword Offer 57. Two Numbers with Sum S - LeetCode