LeetCode |
您所在的位置:网站首页 › leetcode和acm相比 › LeetCode |
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]解法一:思路:直接两个for循环暴力搜索符合条件返回 但时间复杂度太高了,为O(n^2) 解法二: 参考网上的思路: 首先把数组对应target的结果计算出来 如:nums = [2, 7, 11, 15], target = 9 依此计算出map={7:0,2:1,-2:2,-6:3}; 其中key为结果,value为索引 然后再遍历数组,依次取出,如第一个:nums(0) = 2,所以去map中查看是否有key为2的结果, 如果查出有对应的结果,说明找到了相加等于target的两个数, 对应的索引分别是:遍历的i,map中对应的value值; 时间复杂度:O(n) |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |