Two Sum

1. 问题描述

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.

Example:

Given nums = [2, 7, 11, 15], target = 9,

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

2. 求解

解法一

这个题最简单也是最容易的就是两层循环遍历,这个没什么可说的,时间复杂度为O(n^2)。

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

Leetcode Accepted,Runtime: 45 ms。

解法二

思考一下,如何进行优化呢?首先,条件为nums[i] + nums[j] = target,已知target和nums[i]的情况下,能不能直接确定nums[j]在数组中是否存在呢?这是可以的,很容易想到map结构,当然数据结构要变换一下,而map的查询复杂度为O(1),map结构的设计有两种,要不是key为整数,要不key为整数的索引。由于我们求的是整数的索引,因此应该将key设为整数,value为整数的索引。但key为整数有一个问题就是,如果数组中存在相同整数,则后一个放入的数值会覆盖前一个,因此需要单独处理。题目中明确说了一个输入只有一个解,因此如果出现两个整数相等的情况,只需要找到另一个数字的索引即可。

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int result[] = new int[2];
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i = 0; i < n; i++) {
            int other = target - nums[i];
            map.put(nums[i], i);
            if(map.containsKey(other)) {
                //两个数字不等情况
                if(other != nums[i]) {
                    //注意顺序
                    result[0] = map.get(other);
                    result[1] = i;
                    break;
                }else {
                    //数字相等情况
                    result[0] = i;
                    for(int j = i + 1; j < n; j++) {
                        if(nums[j] == other) {
                            result[1] = j;
                            return result;
                        }
                    }  
                }
            }
        }
        return result;
    }
}

Leetcode Accepted,Runtime: 12 ms。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Single Number III

    Tyan
  • Leetcode 45. Jump Game II

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.csdn....

    Tyan
  • Leetcode 220. Contains Duplicate III

    版权声明:博客文章都是作者辛苦整理的,转载请注明出处,谢谢! https://blog.cs...

    Tyan
  • 两数之和(TwoSum)

    我工作2年已经感觉到危机感,正准备同时这面临着两个问题了,不如蹭现在还有来得及一起去把算法练起来吧,光看可不行得练。尽可能的把 https://leetcode...

    爱敲代码的猫
  • 两数之和(TwoSum)

    我工作2年已经感觉到危机感,正准备同时这面临着两个问题了,不如蹭现在还有来得及一起去把算法练起来吧,光看可不行得练。尽可能的把 https://leetcode...

    爱敲代码的猫
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • leetcode哈希表之两数之和

    这里利用HashMap来存储目标值与当前值的差值及其索引,遍历nums数组,遇到存在的key则直接返回。

    codecraft
  • Single Number III

    Tyan
  • leetcode-easy-array-两数之和

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

    shengjk1
  • leetcode哈希表之好数对的数目

    这里先利用HashMap统计一下元素的个数,根据一个数出现了n次的话,这个数的好数对就是n*(n-1)/2来计算结果。

    codecraft

扫码关注云+社区

领取腾讯云代金券