Visit original link: 1. Two Sum - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions for a better experience!

LeetCode link: 1. Two Sum, difficulty: Easy.

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Explanation:

Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6

Output: [1,2]

Input: nums = [3,3], target = 6

Output: [0,1]

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• Only one valid answer exists.

1. The time complexity of the brute force solution is O(n^2). To improve efficiency, you can sort the array, and then use two pointers, one pointing to the head of the array and the other pointing to the tail of the array, and decide left += 1 or right -= 1 according to the comparison of sum and target.

2. After sorting an array of numbers, if you want to know the original index corresponding to a certain value, there are two solutions:

• Time complexity: O(N * log N).
• Space complexity: O(N).

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_index_list = [(num, i) for i, num in enumerate(nums)]
        num_index_list.sort()

        left = 0
        right = len(nums) - 1

        while left < right:
            sum_ = num_index_list[left][0] + num_index_list[right][0]
            
            if sum_ == target:
                return [num_index_list[left][1], num_index_list[right][1]]

            if sum_ < target:
                left += 1
                continue

            right -= 1

// Welcome to create a PR to complete the code of this language, thanks!

1. In Map, key is num, and value is array index.
2. Traverse the array, if target - num is in Map, return it. Otherwise, add num to Map.

1. In Map, key is num, and value is array index.

   let numToIndex = new Map()
   
   for (let i = 0; i < nums.length; i++) {
     numToIndex.set(nums[i], i)
   }

2. Traverse the array, if target - num is in Map, return it. Otherwise, add num to Map.

   let numToIndex = new Map()
   
   for (let i = 0; i < nums.length; i++) {
     if (numToIndex.has(target - nums[i])) { // 1
       return [numToIndex.get(target - nums[i]), i] // 2
     }
   
     numToIndex.set(nums[i], i)
   }

• Time complexity: O(N).
• Space complexity: O(N).

class Solution {
    public int[] twoSum(int[] nums, int target) {
        var numToIndex = new HashMap<Integer, Integer>();
  
        for (var i = 0; i < nums.length; i++) {
            if (numToIndex.containsKey(target - nums[i])) {
                return new int[]{numToIndex.get(target - nums[i]), i};
            }

            numToIndex.put(nums[i], i);
        }

        return null;
    }
}

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        
        for i, num in enumerate(nums):
            if target - num in num_to_index:
                return [num_to_index[target - num], i]

            num_to_index[num] = i

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> num_to_index;
  
        for (auto i = 0; i < nums.size(); i++) {
            if (num_to_index.contains(target - nums[i])) {
                return {num_to_index[target - nums[i]], i};
            }

            num_to_index[nums[i]] = i;
        }

        return {};
    }
};

var twoSum = function (nums, target) {
  let numToIndex = new Map()
  
  for (let i = 0; i < nums.length; i++) {
    if (numToIndex.has(target - nums[i])) {
      return [numToIndex.get(target - nums[i]), i]
    }

    numToIndex.set(nums[i], i)
  }
};

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        var numToIndex = new Dictionary<int, int>();
  
        for (int i = 0; i < nums.Length; i++) {
            if (numToIndex.ContainsKey(target - nums[i])) {
                return [numToIndex[target - nums[i]], i];
            }

            numToIndex[nums[i]] = i;
        }

        return null;
    }
}

func twoSum(nums []int, target int) []int {
    numToIndex := map[int]int{}

    for i, num := range nums {
        if index, ok := numToIndex[target - num]; ok {
            return []int{index, i}
        }

        numToIndex[num] = i
    }

    return nil
}

def two_sum(nums, target)
  num_to_index = {}

  nums.each_with_index do |num, i|
    if num_to_index.key?(target - num)
      return [num_to_index[target - num], i]
    end

    num_to_index[num] = i
  end
end

// Welcome to create a PR to complete the code of this language, thanks!

1. The time complexity of the brute force solution is O(n^2). To improve efficiency, you can sort the array, and then use two pointers, one pointing to the head of the array and the other pointing to the tail of the array, and decide left += 1 or right -= 1 according to the comparison of sum and target.
2. After finding the two values which sum is target, you can use the index() method to find the index corresponding to the value.

• Time complexity: O(N * log N).
• Space complexity: O(N).

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        original_nums = nums.copy()
        nums.sort()

        left = 0
        right = len(nums) - 1

        while left < right:
            sum_ = nums[left] + nums[right]

            if sum_ == target:
                break

            if sum_ < target:
                left += 1
                continue

            right -= 1

        return [
            original_nums.index(nums[left]),
            len(nums) - 1 - original_nums[::-1].index(nums[right])
        ]

// Welcome to create a PR to complete the code of this language, thanks!

Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website LeetCode.to: Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!

Original link: 1. Two Sum - LeetCode Python/Java/C++/JS/C#/Go/Ruby Solutions.

GitHub repository: leetcode-python-java.