Leetcode---两数之和1
本文最后更新于:2021年8月8日 下午
Leetcode—两数之和1
给定一个整数数组nums和一个正阿虎目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标
你可以假设每种输入只会对应一个答案,但是,数组中同一个元素不能使用两遍。
示例:
nums = [2,7,11,15],target = 9;
输出:[0,1]
解法一:暴力法
class Solution {
// Brute Force
// N is the size of nums
// Time Complexity: O(N^2)
// Space COmplexity: O(1)
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
int sum = nums[i] + nums[j];
if (sum == target) {
result[0] = i;
result[1] = j;
return result;
}
}
}
return result;
}
}
解法二:哈希表法
class Solution {
// HashMap
// N is the size of nums
// Time Complexity: O(N)
// Space COmplexity: O(N)
public int[] twoSum(int[] nums, int target) {
int[] result = new int[2];
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int j = 0; j < nums.length; j++) {
int diff = target - nums[j];
if (map.containsKey(diff) && map.get(diff) != j) {
result[0] = j;
result[1] = map.get(diff);
return result;
}
}
return result;
}
}
本文作者: CodeAnime
本文链接: https://codeanime.cc/Leetcode-%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C1.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!