Two Sum Problem – Find Indices of Numbers Adding to a Target Value

On Valentine’s Day, programmers are encouraged to celebrate by combining literary flair with coding skills, leading into the classic algorithmic challenge known as the Two Sum problem.

The task is to find two distinct indices in an integer array nums such that the sum of the elements at those indices equals a given integer target . It is guaranteed that exactly one solution exists and each element may be used at most once.

Constraints

2 ≤ nums.length ≤ 10⁴

-10⁹ ≤ nums[i] ≤ 10⁹

-10⁹ ≤ target ≤ 10⁹

Only one valid answer exists.

Example cases

<code>Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9</code>

<code>Input: nums = [3,2,4], target = 6
Output: [1,2]</code>

<code>Input: nums = [3,3], target = 6
Output: [0,1]</code>

Solution approach – Brute‑force enumeration

The simplest method iterates over each element x in the array and searches for target - x among the subsequent elements, ensuring no element is used twice.

Java implementation

<code>class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
}</code>

C++ implementation

<code>class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};
    }
};</code>

C implementation

<code>int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    for (int i = 0; i < numsSize; ++i) {
        for (int j = i + 1; j < numsSize; ++j) {
            if (nums[i] + nums[j] == target) {
                int* ret = malloc(sizeof(int) * 2);
                ret[0] = i; ret[1] = j;
                *returnSize = 2;
                return ret;
            }
        }
    }
    *returnSize = 0;
    return NULL;
}</code>

Python3 implementation

<code>class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        n = len(nums)
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]
        return []</code>

Go implementation

<code>func twoSum(nums []int, target int) []int {
    for i, x := range nums {
        for j := i + 1; j < len(nums); j++ {
            if x+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}</code>

Complexity analysis

Time complexity: O(N²), where N is the number of elements in the array.

Space complexity: O(1) (excluding input and output).

The article concludes with a friendly reminder to practice the solution and invites readers to explore additional Python learning resources.