剑指offer - 和为S的两个数字(Java实现)
思路一:首先第一反应就是二分,一个有序数组,和为S的两个数,比较经典的二分题目,直接遍历数组,每一个项的值为 val,使用二分的方法直接判断 S - val 是否在这个数组中即可。
import java.util.ArrayList; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { int Min = Integer.MAX_VALUE, n = array.length; ArrayList<Integer> list = new ArrayList<>(); int x1 = 0, y1 = 0; for(int val : array) { if(binary_serach(array, sum - val)) { if(Min > val * (sum - val)) { Min = val * (sum - val); x1 = val; y1 = sum - val; } } } if(x1 != 0) list.add(x1); //需要注意最后没有找到的情况 if(y1 != 0) list.add(y1); return list; } public boolean binary_serach(int[] array, int val) { int l = 0, r = array.length - 1; while(l <= r) { int mid = (l + r) >> 1; if(array[mid] < val) { l = mid + 1; } else if(array[mid] > val) { r = mid - 1; } else return true; } return false; } }
思路二:双指针,我们设置两个指针,一个指向最左边 l,一个指向最右边 r,那么有下面三种情况。
- array[l] + array[r] = sum, 此结果即为一组合法的答案,如果我们想要找到其他的答案我们需要:--i, ++ j, 继续寻找其他答案。
- array[l] + array[r] < sum, 说明结果偏小,那么答案需要偏大,我们需要 ++ i。
- array[l] + array[r] > sum, 说明结果偏大,那么答案需要偏小,我们需要 -- j。
import java.util.ArrayList; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { int Min = Integer.MAX_VALUE, n = array.length; ArrayList<Integer> list = new ArrayList<>(); int x1 = 0, y1 = 0; int i = 0, j = n - 1; while(i < j) { if(array[i] + array[j] == sum) { if(Min > array[i] * array[j]) { Min = array[i] * array[j]; x1 = array[i]; y1 = array[j]; } ++ i; -- j; } else if(array[i] + array[j] < sum) ++ i; else if(array[i] + array[j] > sum) -- j; } if(x1 != 0) list.add(x1); if(y1 != 0) list.add(y1); return list; } }
【剑指offer】题目全解 文章被收录于专栏
本专栏主要是刷剑指offer的题解记录