1つのインクリメンタルソートの配列と1つの数字Sを入力し、配列の中で2つの数を検索し、彼らの和がちょうどSであるようにし、複数の数字の和がSに等しい場合、2つの数の積が最小になるように出力します.出力説明:各テストケースに対応して、2つの数を出力し、小さな先出力を出力します.
2526 ワード
1つのインクリメンタルソートの配列と1つの数字Sを入力し、配列の中で2つの数を検索し、彼らの和がちょうどSであるようにし、複数の数字の和がSに等しい場合、2つの数の積が最小になるように出力します.
出力の説明:
1.暴力法遍歴:(accept)分かりやすく、暴力について、時間の複雑さの要求がなければ直接このようにすることができて、論理がはっきりしていて、すぐに書くことができます.
2.左右に挟む方法で、時間の複雑さがO(n)であることも分かりやすいが、やはり暴力法がないと考えやすい(ブロガーのようなクズには、多く見たり、蓄積したりする必要がある)
リンク:https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b出典:牛客網
数列はインクリメントを満たし、2つのヘッダとテールの2つのポインタiとjを設定する.
ai+aj==sumなら、答えです(差が遠ければ遠いほど積が小さくなります)
ai+aj>sumの場合、ajは答えの1つではないに違いない(前にiの前の数が得られない)、j-=1
ai+ajO(n)証明:
見つかった最初のグループ(差が最も大きい)は、積が最も小さいことです.x+y=C(Cは定数)を考慮してx*yの大きさを証明できる.y>=x、y-x=d>=0、すなわちy=x+d、2 x+d=C、x=(C-d)/2、x*y=x(x+d)=(C-d)(C+d)/4=(C^2-d^2)/4、すなわちx*yは変数dに関する二次関数であり、対称軸はy軸であり、開口は下向きである.dは>=0であり,dが大きいほどx*yも小さくなる.
コード:
出力の説明:
， ， 。1.暴力法遍歴:(accept)分かりやすく、暴力について、時間の複雑さの要求がなければ直接このようにすることができて、論理がはっきりしていて、すぐに書くことができます.
import java.util.ArrayList;
import java.util.List;
public class Solution {
public ArrayList FindNumbersWithSum(int [] array,int sum) {
ArrayList list = new ArrayList();
String two_int = new String();
int min_Mul = Integer.MAX_VALUE;
for(int i = 0; i < array.length; i++)
for(int j = array.length-1; j > i; j--)
{
if((array[i] + array[j] == sum)&&(array[i] * array[j] < min_Mul))
{
two_int = "";
two_int = String.valueOf(array[i]) +" "+String.valueOf(array[j]);
min_Mul = array[i] * array[j];
break;
}
}
if(two_int.length() == 0)
return list;
String[] strarr = two_int.split(" ");
list.add(Integer.parseInt(strarr[0]));
list.add(Integer.parseInt(strarr[1]));
return list;
}
} 2.左右に挟む方法で、時間の複雑さがO(n)であることも分かりやすいが、やはり暴力法がないと考えやすい(ブロガーのようなクズには、多く見たり、蓄積したりする必要がある)
リンク:https://www.nowcoder.com/questionTerminal/390da4f7a00f44bea7c2f3d19491311b出典:牛客網
数列はインクリメントを満たし、2つのヘッダとテールの2つのポインタiとjを設定する.
ai+aj==sumなら、答えです(差が遠ければ遠いほど積が小さくなります)
ai+aj>sumの場合、ajは答えの1つではないに違いない(前にiの前の数が得られない)、j-=1
ai+aj
見つかった最初のグループ(差が最も大きい)は、積が最も小さいことです.x+y=C(Cは定数)を考慮してx*yの大きさを証明できる.y>=x、y-x=d>=0、すなわちy=x+d、2 x+d=C、x=(C-d)/2、x*y=x(x+d)=(C-d)(C+d)/4=(C^2-d^2)/4、すなわちx*yは変数dに関する二次関数であり、対称軸はy軸であり、開口は下向きである.dは>=0であり,dが大きいほどx*yも小さくなる.
コード:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public ArrayList FindNumbersWithSum(int [] array,int sum) {
ArrayList list = new ArrayList();
if (array == null || array.length < 2)
return list;
for(int i = 0, j = array.length-1; i < j; )
{
if(array[i]+array[j]==sum)
{
list.add(array[i]);
list.add(array[j]);
return list;
}
else if(array[i]+array[j]>sum)
j--;
else{
i++;
}
return list;
}
}