剑指offer-42、和为S的两个数字
<h2 id="题描述">题⽬描述</h2><p>输⼊⼀个递增排序的数组和⼀个数字 S ，在数组中查找两个数，使得他们的和正好是 S ，如果有多对数字的和等于 S ，输出两个数的乘积最⼩的。</p>
<p>返回值描述：对应每个测试案例，输出两个数，⼩的先输出。</p>
<p>输⼊：,15<br>
返回值：</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴遍历">暴⼒遍历</h3>
<p>直接遍历每两个数，查看其和是否符合等于 sum ,再计算其乘积，是否⼩于之前的乘积，如果⼩于，则更新。</p>
<pre><code class="language-java">public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
ArrayList<Integer> results = new ArrayList<>();
long mutip = 999999999;
if (array != null && array.length > 2) {
for (int i = 0; i < array.length - 1; i++) {
for (int j = i + 1; j < array.length; j++) {
if (array + array == sum && array * array < mutip) {
results.clear();
results.add(array);
results.add(array);
mutip = array * array;
} else if (array + array > sum) {
break;
}
}
}
}
return results;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n²)，需要检查所有可能的数对组合</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数级别额外空间</li>
</ul>
<h3 id="使hashset">使⽤HashSet</h3>
<p>针对每⼀个数字 a ，都查看 hashset 中是否存在 sum-a ，同时把该数字添加到 set 中。如果存在则计算其乘积，更新乘积最⼩值。</p>
<pre><code class="language-java">public ArrayList<Integer> FindNumbersWithSum1(int[] array, int sum) {
ArrayList<Integer> results = new ArrayList<>();
long mutip = 999999999;
HashSet<Integer> set = new HashSet<>();
if (array != null && array.length > 2) {
for (int i = 0; i < array.length; i++) {
if (set.contains(sum - array) && array*(sum - array) < mutip) {
results.clear();
results.add(sum-array);
results.add(array);
mutip = array * (sum - array);
}
set.add(array);
}
}
return results;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，只需遍历数组一次</li>
<li><strong>空间复杂度</strong>：O(n)，需要HashSet存储元素</li>
</ul>
<h3 id="双指针法最优">双指针法（最优）</h3>
<p>利用数组有序特性：左右指针分别指向数组首尾，根据当前和动态调整指针位置</p>
<p>由于数组 nums[] 是有序的，也就是第⼀个数字是最⼩的，第⼆个数字是最⼤的，那么我们使⽤⼀个指针 i 指向数组第⼀个元素，⼀个指针 j 指向数组最后⼀个元素。</p>
<p>i 指针往右边移动， j 指针往左边移动，直到两者相撞（相等）。</p>
<p>如果 nums+nums == sum ,那么说明这个是可能存在的解，需要计算两者的乘积，如果⽐保存的乘积还⼩，则更新结果。同时左边指针 i 往右边移动⼀位，右边指针 j 往左边移动⼀位。</p>
<p>如果 nums + nums > sum ,则说明和太⼤了，⽐ sum 还要⼤，则右边的指针j需要左移⼀步，即是 j-- 。</p>
<p>如果 nums + nums < sum ,则说明和太⼩了，⽐ sum 还要⼩，则左边的指针i需要左移⼀步，即是 i++ 。</p>
<pre><code class="language-java">public ArrayList<Integer> FindNumbersWithSum2(int[] array, int sum) {
ArrayList<Integer> results = new ArrayList<>();
long mutip = 999999999;
if (array != null && array.length > 2) {
int left = 0,right = array.length-1;
while(left<right){
if(array+array==sum){
if(array*array<mutip){
mutip = array*array;
results.clear();
results.add(array);
results.add(array);
}
left++;
right--;
}else if(array+array>sum){
right--;
}else{
left++;
}
}
}
return results;
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，最坏情况下左右指针共同遍历整个数组</li>
<li><strong>空间复杂度</strong>：O(1)，只使用固定数量的指针变量</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19256982
頁:
[1]