?LeetCode刷題實(shí)戰(zhàn)170：兩數(shù)之和 III - 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)
Design and implement a TwoSum class. It should support the following operations: add
and find.
add(input) – Add the number input to an internal data structure.
find(value) – Find if there exists any pair of numbers which sum is equal to the value.
題意
示例 1:
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
示例 2:
add(3); add(1); add(2);
find(3) -> true
find(6) -> false
解題
在類下面聲明屬性
在構(gòu)造函數(shù)方法里初始化類的屬性
在其他函數(shù)對(duì)屬性和函數(shù)進(jìn)行調(diào)用完成功能
class?TwoSum?{
????????//屬性
????????private?ArrayListnums;
????????private?boolean is_sorted;
????/** Initialize your data structure here. */
????public?TwoSum(){
????????this.nums = new?ArrayList();
????????is_sorted =false;
????}
????/** Add the number to an internal data structure.. */
????public?void?add(int?number) {
????????this.nums.add(number);
????????this.is_sorted = false;
????}
????
????/** Find if there exists any pair of numbers which sum is equal to the value. */
????public?boolean find(int?value) {
?????????if?(!this.is_sorted) {
??????//調(diào)用Collections類進(jìn)行數(shù)組排序
??????Collections.sort(this.nums);
????}
????int?low = 0, high = this.nums.size() - 1;
????while?(low < high) {
??????int?twosum = this.nums.get(low) + this.nums.get(high);
??????if?(twosum < value)
????????low += 1;
??????else?if?(twosum > value)
????????high -= 1;
??????else
????????return?true;
????}
????//默認(rèn)返回false
????return?false;
????}
}