两数之和

CategoryDifficultyLikesDislikes
algorithmsEasy (48.83%)8516-

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

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

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

Discussion | Solution

解法【暴力遍历】

读题

实质上就是在一个数组中查找两个数的和为指定值
且不可以自己加自己【数组中同一个元素不能使用两遍】
有一点疑问在于,如果没有结果如何输出?
由于反馈没有得到回复,我也就没有处理这种情况了。

解法

直接暴力遍历数组吧,思路是
给定值-当前值=剩余值
在后面的数组中找到剩余值,返回下标

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        int[] res=new int[2];
        int i=0;
        foreach(var nowItem in nums){
            //最后一位不用遍历,后面没有数了
            if(i==nums.Length){
                return res;
            }
            //剩余值
            int remain=target-nowItem;
            //从下一个下标开始遍历,到末尾结束
            for(int nowIndex=i+1;nowIndex<nums.Length;nowIndex++){
                if(nums[nowIndex]==remain){
                    //找到了,赋值下标
                    res[0]=i;
                    res[1]=nowIndex;
                    return res;
                }
            }
            i++;
        }
        return res;
    }
}

思考

时间复杂度: O(n^2)【长度为n的数组两层遍历,一次为n,嵌套两次为n^2】
空间复杂度: O(1)

以空间换时间
可以使用字典进行单次遍历查找,以减少时间复杂度
实现时间及空间复杂度O(n),但是要注意数组中出现相同值如[1,2,2,3,3]这种情况

膜拜大佬

如果大佬们有更好的解法,不如评论分享赐教~
我的Leetcode解题代码库

本文作者:Author:     文章标题:【LeetCode】1.两数之和
本文地址:https://traceless.site/index.php/archives/30/     
版权说明:若无注明,本文皆为“Traceless”原创,转载请保留文章出处。
Last modification:June 29th, 2020 at 03:30 pm
如果觉得我的文章对你有用,请随意赞赏