这是悦乐书的第179次更新，第181篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第38题（顺位题号是167）。给定已按升序排序的整数数组，找到两个数字，使它们相加到特定的目标数。函数twoSum应该返回两个数字的索引，使它们加起来到目标，其中index1必须小于index2。
注意：
-
返回的答案（index1和index2）不是从零开始的。
-
可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。
例如：
输入：数字= [2,7,11,15]，目标= 9
输出：[1,2]
说明：2和7之和为9.因此index1 = 1，index2 = 2。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
此题和LeetCode算法题的第一题Two Sum类似，不过此题定义和条件更加清晰，规定了只存在唯一解,并且将数组进行了排序。
和以前一样，第一种解法是暴力解法，使用双层循环，依次遍历相加判断和是否等于目标值，直到找到两元素为止。但是元素的索引需要加1，因为题目要求索引不从0开始。
特殊情况：当数组为空或者其长度小于2时，直接返回空。
public int[] twoSum (int[] numbers, int target) {
if (numbers == null || numbers.length < 2) {
return null;
}
int[] index = new int[2];
for(int i = 0; i < numbers.length; i++) {
for(int j = i+1; j < numbers.length; j++) {
if (numbers[i] + numbers[j] == target) {
index[0] = i+1;
index[1] = j+1;
}
}
}
return index[0] == 0 ? null : index;
}
此解法时间复杂度是O(n^2)，空间复杂度是O(1)。
03 第二种解法
使用HashMap，遍历数组时，判断当前元素和目标值之间的差值是否存在map中，如果存在，就返回map中此元素的value，即其索引，和当前元素的索引；否则，将当前元素作为key，索引作为value存入map中，然后进行下一次循环。
特殊情况：当数组为空或者其长度小于2时，直接返回空。
public int[] twoSum2 (int[] numbers, int target) {
if (numbers == null || numbers.length < 2) {
return null;
}
int[] index = new int[2];
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for (int k=0; k<numbers.length; k++) {
if (map.containsKey(target-numbers[k])) {
index[0] = map.get(target-numbers[k]);
index[1] = k+1;
}
map.put(numbers[k], k+1);
}
return index[0] == 0 ? null : index;
}
时间复杂度是O(n)，空间复杂度是O(n)。
04 第三种解法
既然数组已经是排过序的，使用双指针，每次从前往后和从后往前各取一个元素，判断两数之和是否等于目标值，如果小于目标值，则从前往后的指针向前移动一位；如果大于目标值，则从后往前的指针向前移动一位，直到两数之和等于目标值即可。
特殊情况：当数组为空或者其长度小于2时，直接返回空。
public int[] twoSum3(int[] numbers, int target) {
if (numbers == null || numbers.length < 2) {
return null;
}
int start = 0;
int end = numbers.length - 1;
while (start < end) {
int sum = numbers[start] + numbers[end];
if (sum == target) {
return new int[] {start+1, end+1};
} else if (sum < target) {
start++;
} else {
end--;
}
}
return null;
}
此解法的时间复杂度是O(n)，空间复杂度是O(1)。
05 小结
算法专题目前已连续日更超过一个月，算法题文章38+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论