java给定一个整数组 nums 和一个整数目标值 target ,请你在该数组中找出 和为目标值 target 的那两 整数,并它们的数组下标. 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
时间: 2023-11-16 09:44:21 浏览: 110
你可以使用一种双指针的方法来解决这个问题。首先,创建一个哈希表(HashMap)用来存储数组元素及其对应的索引值。
然后,使用两个指针i和j分别指向数组的第一个元素和最后一个元素。在每一次循环中,通过判断当前指向的两个元素之和与目标值的大小关系,来决定移动哪个指针。
如果当前指向的两个元素之和等于目标值,则返回它们的索引。
如果当前指向的两个元素之和小于目标值,则将指针i向右移动一位。
如果当前指向的两个元素之和大于目标值,则将指针j向左移动一位。
重复上述步骤,直到找到满足条件的两个元素或者遍历完整个数组。
以下是对应的Java代码实现:
```java
import java.util.HashMap;
public class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
```
这段代码的时间复杂度为O(n),其中n是数组的长度。
阅读全文