给定一个整数数组,返回两个数字的索引,使它们相加达到特定目标。
示例:
给定数字 =
,目标 = 6,[3, 2, 4]
因为
= 2 + 4 = 6nums[1] + nums[2]
.return [1, 2]
解决方案
var twoSum = function(nums, target) {
for(let i = 0; i <= nums.length; i++){
for(let j = 0; j <= nums.length; j++){
if(nums[i] + nums[j] == target){
return [i, j]
}
}
}
};
上面的代码适用于其他情况,但不适用于这种情况。
预期结果
[1,2]
输出
[0,0]
例如,我尝试使用不同的数字数组和不同的目标,即使您更改数字的顺序它也能工作
示例:
新数组:
[15, 7, 11, 2]
,目标 = 9,
输出:
[1, 3]
。
我不明白该解决方案有什么问题,希望有人能解释一下。谢谢
您可以使用非常简单的技术。
基本上,您可以检查数组中是否存在目标与当前迭代中的元素的差异。
假设相同的索引不能使用两次
nums = [3, 2, 4], target = 6
nums[0] = 3
target = 6
diff = 6 - 3 = 3
nums.indexOf[3] = 0 // FAILURE case because it's the same index
// move to next iteration
nums[1] = 2
target = 6
diff = 6 - 2 = 4
nums.indexOf(4) = 2 // SUCCESS '4' exists in the array nums
// break the loop
这是 leetcode 接受的答案。
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
for (let index = 0; index < nums.length; index++) {
const diff = target - nums[index];
const diffIndex = nums.indexOf(diff);
// "diffIndex !== index" takes care of same index not being reused
if (diffIndex !== -1 && diffIndex !== index) {
return [index, diffIndex];
}
}
};
运行时间:72 ms,比 93.74% 的 JavaScript 在线提交的 Two Sum 还要快。
内存使用量:38.5 MB,低于 JavaScript 在线提交的 Two Sum 的 90.55%。
有人可以帮助我减少内存使用吗?
我不明白该解决方案有什么问题,我希望 有人可以解释一下吗?
在这里,内部和外部循环都从
0
th开始,因此在[3,2,4] and target 6
的情况下,它将返回[0,0]
,因为3 + 3
等于目标,因此要注意相同的索引元素不被使用两次会在外循环和内循环之间产生 1
的差异
使外循环从第
0
th索引开始,内循环以值i+1
开始
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i++){
for(let j = i+1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
return [i, j]
}
}
}
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
这里有一个简单的方法来解决这个问题,并且使用 JavaScript 使用不同类型的输入非常有效。
就像输入
([3,3], 6)
一样,其预期输出将为 [0,1]
,而像 ([3,2,4], 6)
这样的输入,预期输出将为 [2,4]
var twoSum = function (nums, target) {
for (let i = 0; i <= nums.length; i++) {
for (let j = 0; j <= nums.length; j++) {
if (i !== j) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
}
};
console.log(twoSum([3, 2, 4], 6));
我们可以使用地图/对象在 O(n) 内解决这个问题。 我们可以维护一个映射或对象,它将用索引保存所有值,然后我们可以迭代数组并找到每个值的 target-nums[i] ,并在映射/对象中找到该值。 让我们通过例子来看看:-
nums=[2,7,11,15]
target = 9;
then map/object will be
mm={
2 : 0,
7: 1,
11: 2,
15: 3
}
then for each value, we will find diff and find that diff in map/object.
for i=0 diff= 9-2=7 and mm.has(7) is true so our answer is 2 and 7.
for their index we can use mm.get(7) and i.
return [mm.get(7), i]
var twoSum = function(nums, target) {
let mm=new Map();
for(let i=0;i<nums.length;i++){
mm.set(nums[i],i);
}
let diff=0;
let j;
for(let i=0;i<nums.length;i++){
diff=target-nums[i];
if(mm.has(diff) && i!=mm.get(diff)){
j=mm.get(diff);
if(j>i){
return [i,j];
}else{
return [j,i];
}
}
}
};
运行时间:76 毫秒,比 88.18% 的 JavaScript 在线提交的 Two Sum 更快。 内存使用量:41.4 MB,低于 JavaScript 在线提交的 Two Sum 的 13.32%。
您的解决方案按预期工作。对于
nums = [3, 2 ,4]
和 target = 6
,[0, 0]
是针对 nums[0] + nums[0] = 3 + 3 = 6
所概述问题的有效解决方案。
如果您需要两个不同的索引(据我了解,任务不需要这),您可以添加额外的不平等检查(
nums[i] + nums[j] == target && i != j
)。
var twoSum = function(nums, target) {
for(let i=0; i<nums.length; i++){
for(let j=i+1; j<nums.length; j++){
if(nums[j] === target - nums[i]){
return [i, j];
}
}
}
};
var twoSum = function (nums, target) {
var len = nums.length;
for (var i = 0; i < len; i++) {
for (var j = i + 1; j < len; j++) {
if (nums[i] + nums[j] == target) {
return [i,j];
}
}
}
};
var twoSum = function(nums, target) {
for(var i=0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
temp = nums[i]+nums[j];
if(temp == target){
return [i,j]
}
}
}
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
console.log(twoSum([3,3],6))
效果非常好,运行时间:72 毫秒小于 84 毫秒
以 O(n) 时间复杂度解决此问题的另一种有效解决方法是不使用嵌套循环。我对这些步骤进行了注释,以便 JS 开发人员可以轻松理解。这是我使用 golang 的解决方案:
func twoSum(intArray []int, target int) []int {
response := []int{-1, -1} // create an array as default response
if len(intArray) == 0 { // return default response if the input array is empty
return response
}
listMap := map[int]int{} // create a Map, JS => listMap = new Map()
for index, value := range intArray { // for loop to fill the map
listMap[value] = index
}
for i, value := range intArray { // for loop to verify if the subtraction is in the map
result := target - value
if j, ok := listMap[result]; ok && i != j { // this verify if a property exists on a map in golang. In the same line we verify it i == j.
response[0] = i
response[1] = j
return response
}
}
return response
}
var twoSum = function(nums, target) {
var numlen = nums.length;
for(let i=0; i<=numlen; i++){
for(let j=i+1;j<numlen;j++){
var num1 = parseInt(nums[i]);
var num2 = parseInt(nums[j]);
var num3 = num1 + num2;
if(num3 == target){
return[i,j]
}
}
}
};
我想这可能是一个更好的解决方案。这提供了线性解决方案,而不是嵌套循环。
(PS:indexOf也有点像一个循环,复杂度为O(n))
var twoSum = function (nums, target) {
const hm = {}
nums.forEach((num, i) => {
hm[target - num] = i
})
for (let i = 0; i < nums.length; i++) {
if(hm[nums[i]] !== undefined && hm[nums[i]] !== i) {
return ([hm[nums[i]], i])
}
}
};
var twoSum = function(nums, target) {
for (var i = 0; i < nums.length; i++)
{
if( nums.indexOf(target - nums[i]) !== -1)
{
return [i , nums.indexOf(target - nums[i])]
}
}
};
为了清楚控制台 a 和 b 在内部 for 循环中。这会给你清晰的洞察力
var twoSum = function(nums, target) {
var arr=[];
for(var a=0;a<nums.length;a++){
for(var b=1;b<nums.length;b++){
let c=nums[a]+nums[b];
if(c== target && a != b){
arr[0]=a;
arr[1]=b;
}
}
}
return arr;
};
我的解决方案:
public static Object solution(int[] a, int target){
Set<Integer> s = new HashSet<>();
ArrayList<Integer> indexes = new ArrayList<Integer>();
for (int e : a){
Integer diff = new Integer(target - e);
if(diff>0){
s.add(diff);
}
}
int i = 0;
for (int e : a){
if(s.contains(e)){
indexes.add(i);
}
i++;
}
return indexes;
}
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
comp = target - nums[i]
if comp in nums:
j = nums.index(comp)
if(i!=j):
return [i,j]
var twoSum = function(nums, target) {
for(let i = 0; i < nums.length; i++){
for(let j = i+1; j < nums.length; j++){
if(nums[i] + nums[j] == target){
return [i, j]
}
}
}
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
indx =[]
for i in range(len(nums)):
for j in range(i+1,len(nums)):
if nums[j]==(target-nums[i]):
indx.append(i)
indx.append(j)
return indx
twoSummation = (numsArr, estTarget) => {
for(let index = 0; index < numsArr.length; index++){
for(let n = index+1; n < numsArr.length; n++){
if(numsArr[index] + numsArr[n] == estTarget){
return [index, n]
}
}
}
}
console.log(twoSummation([2,7,11,15], 9))
console.log(twoSummation([3,2,4], 6))
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
var twoSum = function(nums, target) {
for(var i=0;i<nums.length;i++){
for(var j=i+1;j<nums.length;j++){
temp = nums[i]+nums[j];
if(temp == target){
return [nums[i],nums[j]]
}
}
}
};
console.log(twoSum([15, 7, 11, 2],9))
console.log(twoSum([3, 2, 4],6))
console.log(twoSum([3,3],6))
</script>
</body>
</html>
来自我用Java提交的leetcode的解决方案。运行时占前 75%,内存占前 25%。它是 0(n) 但使用外部 HashMap。
import java.util.HashMap;
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> numbers= new HashMap<Integer, Integer>();
for(int i=0; i<nums.length; i++){
int cur = nums[i];
numbers.put(cur, i);
}
for(int i=0; i<nums.length; i++){
//check map for diff of target - cur
int diff = target - nums[i];
if(numbers.containsKey(diff) && numbers.get(diff)!=i){
return new int[]{i, numbers.get(diff)};
}
}
return null;
}
}
function addNumber(num, target) {
let arr = [];
num.every((pv, pi) => {
let diff = target - pv;
let diffIdx = num.indexOf(diff);
if (diffIdx !== -1 && diffIdx !== pi) {
arr.push(pi,diffIdx)
return false;
}
return true;
});
return arr;
}
console.log(
addNumber([4, 0, 1, 9, 7],4)
)
public class Main {
public static void main(String[] args) {
int a[] = { 2, 4, 6 };
for (int i = 0; i <= a.length; i++) {
for (int j = i + 1; j < a.length; j++) {
if (a[i] + a[j] == 10) {
int and[] = { i, j };
System.out.println(Arrays.toString(ans));
}
}
}
}
}
const twoSum = (nums, target) => {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const compliment = target - nums[i];
if (map.has(compliment)) {
return [map.get(compliment), i];
}
map.set(nums[i], i);
}
return [];
};
const nums = [3, 2, 4];
const target = 6;
console.log(twoSum(nums, target));
说明:
该解决方案非常高效,时间复杂度为 O(n)。使用 Map 对象使代码更加惯用,并且可以为大型数据集提供更好的性能。