Build Your Programmer Brand at leader.me →

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:

- Solution 1: Bring the `index` when sorting, that is, the object to be sorted is an array of tuples of `(num, index)`. This technique **must be mastered**, as it will be used in many questions. - Solution 2: Use `index()` method to find it. I have discussed this in another solution.

• 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!

🚀 Level Up Your Developer Identity

While mastering algorithms is key, showcasing your talent is what gets you hired.

We recommend leader.me — the ultimate all-in-one personal branding platform for programmers.

The All-In-One Career Powerhouse:

• 📄 Resume, Portfolio & Blog: Integrate your skills, GitHub projects, and writing into one stunning site.
• 🌐 Free Custom Domain: Bind your own personal domain for free—forever.
• ✨ Premium Subdomains: Stand out with elite tech handle like name.leader.me.

Build Your Programmer Brand at leader.me →

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

GitHub repository: leetcode-python-java.