Leetcode Problem 1 - 两数之和

JimmyzZZ

这个问题我在前天试着提交过，但是由于index使用不当，导致了错误。今天使用双重For循环重写，成功了。
但是内存消耗出奇的大。还需要进一步改善。

题干：

[AppleScript] 纯文本查看 复制代码

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

 

示例 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]
 

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

来源：力扣（LeetCode）
链接：[url]https://leetcode-cn.com/problems/two-sum[/url]

我的题解：

[C#] 纯文本查看 复制代码

public class Solution {
    public int[] TwoSum(int[] nums, int target) {
        int[] result = {0, 0};
        for(int i = 0; i < nums.Length; i++){
            for(int j = 0; j < nums.Length; j++){
                if (nums[i] + nums[j] == target && i != j){                 // i != j是为了防止出现意外，例如输入[3,3] target = 6，因为第一个元素3 + 3 = 6而返回错误的答案。
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

初学C#算法，欢迎交流指正。

skystars

我来发一个C++的题解：
（时间复杂度O(n)）

[C++] 纯文本查看 复制代码

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
	    unordered_map<int, int> a;
	    int ans1, ans2;
	    for (int i = 0; i < nums.size(); i++) {
		    if (a.count(target - nums[i])) { // 判断另一个加数是否被添加到a里面
			    ans1 = a[target - nums[i]]; // 第一个答案等于另一个加数在nums中的位置
			    ans2 = i; // 第二个答案等于这个加数在nums中的位置
			    break; // 找到，结束循环
		    }
		    a[nums[i]] = i; // 将nums中第i个数的值和i加入到a里面
	    }
	    vector<int> ret;
	    ret.push_back(ans1); // 将两个答案加入到一个vector里面
	    ret.push_back(ans2);
	    return ret; // 返回
    }
};

skystars

附上楼上题解的测试结果

这个内存消耗有亿点点大啊...
再放一个时间复杂度为O(n²)的题解

[C++] 纯文本查看 复制代码

class Solution {public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    ret.push_back(i);
                    ret.push_back(j);
                    return ret;
                }
            }
        }
        return ret;
    }
};

测试结果如图：


比O(n)的算法慢了很多

henry217

顶级语句？

xiaomeng

skystars 发表于 2021-10-19 21:40
附上楼上题解的测试结果

这个内存消耗有亿点点大啊...

你这是用啥执行的

skystars

xiaomeng 发表于 2022-2-19 07:45
你这是用啥执行的

当然是Leetcode

xiaomeng

skystars 发表于 2022-2-19 11:53
当然是Leetcode

这个还能干这个用，能执行py嘛

JimmyzZZ

xiaomeng 发表于 2022-2-19 11:56
这个还能干这个用，能执行py嘛

建议自己去看看

xiaomeng

JimmyzZZ 发表于 2022-2-19 11:59
建议自己去看看

行，现在就看看

keykylewu

我来一个Python的：

[Python] 纯文本查看 复制代码

def solve(list,target):
    for i in range(len(list)):
        for j in range(len(list)):
            if list[i-1]+list[j-1]==target and i!=j:
                result=[i-1,j-1]
                break
    return result