题解 | #和为S的两个数字#
和为S的两个数字
http://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b
算法思想一：辅助数组
解题思路：
要求a + b = sum, 如果已知a， 那么b = sum - a
遍历数组设置为a，然后将tmp代替原数组并删除元素a，在新的数组tmp中寻找是否存在 sum-a，最后再通过排序方式查找乘积最小的数据组
图解：
图解：
数组array：[1，2，4，7，11，15]，sum = 15
| 步骤 | i | sum-i | tmp |
| 1 | 1 | 14 | [2，4，7，11，15]，14不在tmp中 |
| 2 | 2 | 13 | [1，4，7，11，15]，13不在tmp中 |
| 3 | 4 | 11 | [1，2，7，11，15]，11在tmp中 |
代码展示：
Python版本
class Solution: def FindNumbersWithSum(self, array, tsum): # write code here if not array&nbs***bsp;not tsum: return [] result = [] for i in array: # 创建一个替代数组 tmp = array tmp.remove(i) if (tsum - i) in tmp: result.append([i, tsum - i]) if result: # 对 result 进行排序，选择乘积最小的一组数据 result.sort(key=lambda x: x[0] * x[1]) result = result[0] result.sort() return result return []
复杂度分析：
时间复杂度O(N)：N表示数组的长度，遍历整个数组
空间复杂度O(N)：额外空间数组tmp
算法思想二：双指针
解题思路：
算法流程：1、初始化： 双指针 i , j 分别指向数组 array 的左右两端 （俗称对撞双指针）。
2、循环搜索： 当双指针相遇时跳出；
计算和 s = array[i] + array[j] ；
若 s > sum ，则指针 j 向左移动，即执行 j = j - 1 ；
若 s < sum ，则指针 i 向右移动，即执行 i = i + 1 ；
若 s = sum，立即返回数组 [array[i], array[j]] ；
3、返回空数组，代表无和为 sum 的数字组合
图解：
代码展示：
JAVA版本
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> res = new ArrayList<>();
int i = 0, j = array.length - 1;
while(i < j) {
int s = array[i] + array[j];
if(s < sum) i++;
else if(s > sum) j--;
else {
res.add(array[i]);
res.add(array[j]);
return res;
}
}
return res;
}
} 复杂度分析：
时间复杂度O(N)：N表示数组的长度，双指针共线遍历整个数组
空间复杂度O(1)：变量 i, j 使用常数大小的额外空间。
查看16道真题和解析
拼多多集团-PDD公司氛围 520人发布
