[Leetcode] Two Sum 两数之和

Description 题目描述

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.

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

你可以按任意顺序返回答案。

Example 1:

1
2
3


Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2


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

Example 3:

1
2


Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

$2 \leq nums.length \leq 103$

$-109 \leq nums[i] \leq 109$

$-109 \leq target \leq 109$

Only one valid answer exists.

1 Two pointer 暴力双指针

最容易想到的方法，两个循环分别遍历第一和第二个数来分别确定每个数，然后返回位置。

Time Complexity 时间复杂度 - $O(n^2)$
Space Complexity 空间复杂度 - $O(1)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


//java code

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

1
2
3
4
5
6
7
8
9


# python code

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

2 HashMap

利用HashMap来使用一个指针达到预想的效果。

Time Complexity 时间复杂度 - $O(n)$
Space Complexity 空间复杂度 - $O(n)$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


//java code

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


# python code

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        length = len(nums)
        for i in range(length):
            temp = nums[i+1:]
            if (target - nums[i]) in temp:
                j = temp.index(target - nums[i])+i+1
                return [i,j]

Link 题目链接

leetcode - two sum

力扣 - 两数之和

Contents