java求数组两数之和
时间: 2024-09-24 09:27:31 浏览: 26
在Java中,如果你想要找出数组中两个元素的和等于给定目标值的第一个元素组合,你可以使用哈希表(HashMap)或者双指针(Two Pointers)算法。这里简单介绍两种常见的解决方案:
1. **哈希表法**:
- 遍历数组,将每个元素作为键(key),其索引作为值(value)存入哈希表。
- 再次遍历数组,对于每个元素,计算目标值减去它的差值,如果这个差值已经在哈希表中,那么找到了一对符合条件的元素。
- 时间复杂度通常为O(n)。
```java
import java.util.HashMap;
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");
}
```
2. **双指针法**:
- 定义两个指针,一个指向数组开头(left),另一个指向结尾(right)。
- 如果两个指针所指的数字之和小于目标值,移动左指针;如果大于目标值,移动右指针。
- 直到找到满足条件的两个数或者两个指针相遇为止。
- 时间复杂度也为O(n),空间复杂度为O(1)。
```java
public int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return new int[]{nums[left], nums[right]};
} else if (sum < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException("No two sum solution");
}
```