友链
姚屹晨

leetcode - [1] Two Sum

2020/04/19

题目描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

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

给你一个数组和一个整数k，计算和为k的两个元素的索引。

Update 2020_0627

无法使用双指针思想的根本原因在于无法获取相应元素代表的初始索引。

Update 2020_0524

本来想尝试使用Two Pointer解这道题的。

实现如下：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int lo = 0, len = nums.length, hi = len - 1;
        while (lo < hi){
            int sum = nums[lo] + nums[hi];
            if (sum == target){
                return new int[]{lo, hi};
            } else if (sum < target){
                lo++;
            } else {
                hi--;
            }
        }
        return null;
    }
}

但是遇到了这个Test Case:

当需要返回原数组中两个元素的下标时，有个前置条件，该数组是有序的！

解法1

首先是暴力解法，时间复杂为O(n^2)，空间复杂度为O(1)，这种解法效率很低，因此不推荐。

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

解法2

借助HashMap，以空间换时间。时间复杂度O(n)，空间复杂度也是O(n)。

存原求差：哈希表中存储元素的原始值，而求目标值与元素的差。

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

Enjoy it!


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory