这是一道 简单 题。
题目来自：https://leetcode.cn/problems/two-sum/
题目
提示：
-
-
-
-
只会存在一个有效答案
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
暴力解法
01
解题思路
最简单的算法思路，2 层循环，当遇到两个数 nums[i]和 nums[j] 的和为 target 的时候，返回对应的下标 i, j。 02
Java 代码实现
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 null;
}
}
03
Go 代码实现
func twoSum(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if nums[i] + nums[j] == target {
return []int{i, j}
}
}
}
return nil
}
04
复杂度分析
时间复杂度为，
空间复杂度为。
哈希表
01
解题思路
创建一个哈希表map，key 为数字本身，value 为下标。 遍历数组中的每一个元素 nums[i], 并寻找与之对应的另一个数字 target – nums[i]：
1. 当map中包含 target – nums[i] 时，说明已找到答案，返回 r 的下标 和当前下标 i。
2. 当map中不包含 target – nums[i] 时，将数字 nums[i] 和其下标 i 放入 map。
02
Java 代码实现
class Solution {
private Map<Integer, Integer> map = new HashMap<>();
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for(int i = 0; i < n; i++){
Integer r = target - nums[i];
if(map.containsKey(r)){
return new int[]{map.get(r), i};
}else{
map.put(nums[i], i);
}
}
return null;
}
}
03
Go 代码实现
func twoSum(nums []int, target int) []int {
hashMap := map[int]int{}
for i, v := range nums {
r := target - v
if j, ok := hashMap[r]; ok {
return []int{j, i}
}
hashMap[v] = i
}
return nil
}
04
复杂度分析
时间复杂度为 。 空间复杂度为 。
双指针
01
解题思路
双指针算法要求必须是排好序的数组，所以首先应当将原数组排序。又因为结果要求返回的是下标，所以排序后仍然需要保留原数组的下标。 分别创建两个指针 left 和 right，然后让 left 指针指向第 0 个数字，也就是最小的数字；让 right 指针指向第 n – 1 个数字，也就是最大的数字。
1. 当nums[left] + nums[right] == target时：返回nums[left]和nums[right]在原数组中的下标。 2. 当nums[left] + nums[right] > target时：需要将nums[left] + nums[right]的值 减小 才能匹配到结果，所以需要将right指针向前移动一步。 3. 当nums[left] + nums[right] < target时：需要将nums[left] + nums[right]的值 增大 才能匹配到结果，所以需要将left指针向后移动一步。
02
Java 代码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
// 二维数组，
// numAndIndex[i][0]存放数字本身
// numAndIndex[i][1]存放数字原始位置
int[][] numAndIndex = new int[n][2];
for(int i = 0; i < n; i++){
numAndIndex[i][0] = nums[i];
numAndIndex[i][1] = i;
}
Arrays.sort(numAndIndex, (ni1, ni2) -> {
return ni1[0] == ni2[0] ? ni1[1] - ni2[1] : ni1[0] - ni2[0];
});
int left = 0, right = n - 1;
while(left < right){
if(numAndIndex[left][0] + numAndIndex[right][0] == target){
return new int[]{numAndIndex[left][1], numAndIndex[right][1]};
}else if(numAndIndex[left][0] + numAndIndex[right][0] > target){
right--;
}else{
left++;
}
}
return null;
}
}
03
Go 代码实现
func twoSum(nums []int, target int) []int {
n := len(nums)
var numAndIndex [][2]int
for i, v := range nums {
numAndIndex = append(numAndIndex, [2]int{v, i})
}
sort.Slice(numAndIndex, func(i, j int) bool {
if numAndIndex[i][0] == numAndIndex[j][0] {
return numAndIndex[i][1] < numAndIndex[j][1]
}else {
return numAndIndex[i][0] < numAndIndex[j][0]
}
})
left, right := 0, n - 1
for left < right {
if numAndIndex[left][0] + numAndIndex[right][0] == target {
return []int{numAndIndex[left][1], numAndIndex[right][1]}
}else if numAndIndex[left][0] + numAndIndex[right][0] > target {
right--
}else{
left++
}
}
return nil
}
04
复杂度分析
时间复杂度为 ，第一个循环共执行N次，第二个循环最多执行N次。
空间复杂度为 ，数组 numAndIndex 长度为N。
END
点个
在看 你最好看
原文始发于微信公众号（i余数）：【算法题解】20. 两数之和
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/193939.html
