Two Sum系列

Two Sum

題目:

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

樣例:

numbers=[2, 7, 11, 15], target=9
return [1, 2]

代碼實現(xiàn):

public class Solution {
    /*
     * @param numbers : An array of Integer
     * @param target : target = numbers[index1] + numbers[index2]
     * @return : [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum(int[] numbers, int target) {
        if (numbers == null || numbers.length == 0) {
            return new int[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
   //     List<Integer> list = new ArrayList<>();
     //   Arrays.sort(numbers);
        for (int i = 0; i < numbers.length; i++) {
            if (map.containsKey(numbers[i])) {
                int[] result = {map.get(numbers[i])+1, i+1};
                return result;
              //  list.add(map.get(numbers[i]));
                //list.add(i+1);
            } else {
                map.put(target-numbers[i], i);
            }
        }
        int[] result = {};
        return result;
    }
}

Two Sum - Greater than target

題目:

Given an array of integers, find how many pairs in the array such that their sum is bigger than a specific target number. Please return the number of pairs.

樣例:

numbers = [2, 7, 11, 15], target = 24. 
Return 1. (11 + 15 is the only pair)

代碼實現(xiàn):

public class Solution {
    /**
     * @param nums: an array of integer
     * @param target: an integer
     * @return: an integer
     */
    public int twoSum2(int[] nums, int target) {
        // Write your code here
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums); 
        int left = 0;
        right = nums.length - 1;
        int count = 0;
        while (left < right) {
            if (nums[left] + nums[right] <= target) {
                left++;
            } else {
                count += right - left;
                right--;
            }
        }  
        return count;
    }
}

Two Sum - Data structure design

題目:

Design and implement a TwoSum class. It should support the following operations: add and find.

  • add - Add the number to an internal data structure.
  • find - Find if there exists any pair of numbers which sum is equal to the value.

樣例 :

add(1); add(3); add(5);
find(4) // return true
find(7) // return false

代碼實現(xiàn):

public class TwoSum {
    private List<Integer> list = null;
    private Map<Integer, Integer> map = null;
    public TwoSum() {
        list = new ArrayList<Integer>();
        map = new HashMap<Integer, Integer>();
    }

    // Add the number to an internal data structure.
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, map.get(number)+1);
        } else {
            map.put(number, 1);
            list.add(number);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (int i = 0; i < list.size(); i++) {
            int num1 = list.get(i), num2 = value - num1;
            if ((num1 == num2 && map.get(num1) > 1)
                || (num1 != num2 && map.containsKey(num2))) {  
                return true;
                }
            }
        return false;
    }
}


// Your TwoSum object will be instantiated and called as such:
// TwoSum twoSum = new TwoSum();
// twoSum.add(number);
// twoSum.find(value);

Two Sum - Input array is sorted

題目:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

  • The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

樣例 :

Given nums = [2, 7, 11, 15], target = 9
return [1, 2]

代碼實現(xiàn):

public class Solution {
    /*
     * @param nums an array of Integer
     * @param target = nums[index1] + nums[index2]
     * @return [index1 + 1, index2 + 1] (index1 < index2)
     * 
     * Two-Pointers
     */
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1;
        while (left < right) {
            if (nums[left] + nums[right] == target) {
                int[] result = new int[2];
                result[0] = left + 1;
                result[1] = right +1;
                return result;
            } else if (nums[left] + nums[right] < target) {
                left++;
            } else {
                right--;
            }
        }
        int[] result = {};
        return result;
    }
}

Two Sum - Unique pairs

題目:

Given an array of integers, find how many unique pairs in the array such that their sum is equal to a specific target number. Please return the number of pairs.

樣例:

Given nums = [1,1,2,45,46,46], target = 47
return 2
1 + 46 = 47 
2 + 45 = 47

代碼實現(xiàn):

public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum6(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        int left = 0;
        int right = nums.length-1;
        int count = 0;
        Arrays.sort(nums);
        while (left < right) {
            if (nums[left]+nums[right] == target) {
                count++;
                left++;
                right--;
                while(left < right && nums[left] == nums[left-1]) {
                    left++;
                }
                while(left < right && nums[right] == nums[right+1]) {
                    right--;
                }
            } else if (nums[left]+nums[right] > target) {
                right--;
            } else {
                left++;
            }
        }
        return count;
    }
}

Two Sum - Closest to target

題目:

Given an array nums of n integers, find two integers in nums such that the sum is closest to a given number, target.
Return the difference between the sum of the two integers and the target.

樣例 :

nums = [-1, 2, 1, -4],target = 4.
最接近值為 1

代碼實現(xiàn):

public class Solution {
    /**
     * @param nums an integer array
     * @param target an integer
     * @return the difference between the sum and the target
     */
    public int twoSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return -1;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        int diff = Integer.MAX_VALUE;
        while (left < right) {
            if (nums[left] + nums[right] < target) {
                diff = Math.min(diff, target-nums[left]-nums[right]);
                left++;
            } else {
                diff = Math.min(diff, nums[left]+nums[right]-target);
                right--;
            }
        }
        return diff;
    }
}

Two Sum-Less than or Equal to target

題目:

Given an array of integers, find how many pairs in the array such that their sum is less than or equal to a specific target number. Please return the number of pairs.

樣例:

Given nums = [2, 7, 11, 15], target = 24. 
Return 5. 
2 + 7 < 24
2 + 11 < 24
2 + 15 < 24
7 + 11 < 24
7 + 15 < 25

代碼實現(xiàn):

public class Solution {
    /**
     * @param nums an array of integer
     * @param target an integer
     * @return an integer
     */
    public int twoSum5(int[] nums, int target) {
        if (nums == null || nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums);
        int left = 0;
        int right = nums.length-1;
        int count = 0;
        while (left < right) {
            while (left < right && nums[left] + nums[right] > target) {
                right--;
            } 
            while (left < right && nums[left] + nums[right] <= target) {
                count += right - start;
                left++;  
            } 
        }
        return count;
    }
}

Two Sum - Difference equals to target

題目:

Given an array of integers, find two numbers that their difference equals to a target value.
where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

樣例:

nums = [2, 7, 15, 24], target = 5
return [1, 2] (7 - 2 = 5)

代碼實現(xiàn):

class Pair {
    int idx;
    int num;
    public Pair(int i, int num) {
        this.idx = i;
        this.num =num;
    }
}
public class Solution {
    /*
     * @param nums an array of Integer
     * @param target an integer
     * @return [index1 + 1, index2 + 1] (index1 < index2)
     */
    public int[] twoSum7(int[] nums, int target) {
                int[] indexs = new int[2];
        if (nums == null || nums.length < 2)
            return indexs;

        if (target < 0)
            target = -target;

        int n = nums.length;
        Pair[] pairs = new Pair[n];
        for (int i = 0; i < n; ++i)
            pairs[i] = new Pair(i, nums[i]);

        Arrays.sort(pairs, new Comparator<Pair>(){
            public int compare(Pair p1, Pair p2){
                return p1.num - p2.num;
            } 
        });

        int j = 0;
        for (int i = 0; i < n; ++i) {
            if (i == j)
                j ++;
            while (j < n && pairs[j].num - pairs[i].num < target)
                j ++;

            if (j < n && pairs[j].num - pairs[i].num == target) {
                indexs[0] = pairs[i].idx + 1;
                indexs[1] = pairs[j].idx + 1;
                if (indexs[0] > indexs[1]) {
                    int temp = indexs[0];
                    indexs[0] = indexs[1];
                    indexs[1] = temp;
                }
                return indexs;
            }
        }
        return indexs;

    }
}

Three-Sum

題目:

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

  • Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
  • The solution set must not contain duplicate triplets.

樣例:

S = {-1 0 1 2 -1 -4}, A solution set is:
(-1, 0, 1)
(-1, -1, 2)

代碼實現(xiàn):

public class Solution {
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
        ArrayList<ArrayList<Integer>> results = new ArrayList<>();
        // 存在相同的數(shù)卿操,則不再加入target
        if (numbers == null || numbers.length < 3) {
            return results;
        }
        Arrays.sort(numbers);
        /*遍歷數(shù)組序目,取一個數(shù)的相反數(shù)做target
        *i < numbers.length-2 保留最后2個芯杀,twoSum
        */
        for (int i = 0; i < numbers.length; i++) {
            if (i > 0 && numbers[i] == numbers[i-1]) {
                continue;
            }
            int left = i+1;
            int right = numbers.length-1;
            int target = -numbers[i];
            twoSum(numbers, left, right,target, results);
        }
        return results;
    }
    private void twoSum(int[] numbers,
                        int left,
                        int right,
                        int target,
                        ArrayList<ArrayList<Integer>> results) {
        while (left < right) {
            if (numbers[left]+numbers[right] == target) {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(-target);
                list.add(numbers[left]);
                list.add(numbers[right]);
                left++;
                right--;
                results.add(list);
                // 去除重復加入的情況
                while (left < right && numbers[left] == numbers[left-1]) {
                    left++;
                }
                while (left < right && numbers[right] == numbers[right+1]) {
                    right--;
                }
            } else if (numbers[left]+numbers[right] > target) {
                right--;
            } else {
                left++;
            }
        }                        
    }
}

3Sum Closest

題目:

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers.

樣例:

array S = [-1 2 1 -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

代碼實現(xiàn):

public class Solution {
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target : An integer
     * @return : return the sum of the three integers, the sum closest target.
     */
    public int threeSumClosest(int[] numbers, int target) {
        if (numbers == null || numbers.length < 3) {
            return -1;
        }
        Arrays.sort(numbers);
        int bestSum = numbers[0]+numbers[1]+numbers[2];
        for (int i = 0; i < numbers.length; i++) {
            int left = i+1;
            int right = numbers.length-1;
            while(left < right) {
                int sum = numbers[i]+numbers[left]+numbers[right];
                if (Math.abs(sum-target) < Math.abs(bestSum-target)) {
                    bestSum = sum;
                } 
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }            
        return bestSum;
    }
}

Four-Sum

題目:

給一個包含 n 個數(shù)的整數(shù)數(shù)組 S,在 S 中找到所有使得和為給定整數(shù) target 的四元組 (a, b, c, d)黑界。
注意事項

  • 四元組 (a, b, c, d) 中,需要滿足 a <= b <= c <= d
  • 答案中不可以包含重復的四元組。

樣例:

例如,對于給定的整數(shù)數(shù)組 S=[1, 0, -1, 0, -2, 2] 和 target=0. 滿足要求的四元組集合為:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

代碼實現(xiàn):

public class Solution {
    /**
     * @param numbers : Give an array numbersbers of n integer
     * @param target : you need to find four elements that's sum of target
     * @return : Find all unique quadruplets in the array which gives the sum of
     *           zero.
     */
    public ArrayList<ArrayList<Integer>> fourSum(int[] numbers, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Arrays.sort(numbers);
        //選擇第一個數(shù)
        for (int i = 0; i < numbers.length - 3; i++) {
            //避免選擇重復的數(shù)
            if (i != 0 && numbers[i] == numbers[i-1]) {
                continue;
            }
            //選擇第二個數(shù)
            for (int j = i+1; j < numbers.length - 2; j++) {
                //避免選擇重復的數(shù)
                //if (j != 0 && numbers[j] == numbers[j-1]) {
                //j的取值應該依i而定
                if (j != i+1 && numbers[j] == numbers[j-1]) {
                    continue;
                }
                int left = j+1;
                int right = numbers.length-1;
                while (left < right) {
                    int sum = numbers[i] + numbers[j] + numbers[left] + numbers[right];
                    if (sum < target) {
                        left++;
                    } else if (sum > target) {
                        right--;
                    } else {
                        ArrayList<Integer> list = new ArrayList<>();
                        list.add(numbers[i]);
                        list.add(numbers[j]);
                        list.add(numbers[left]);
                        list.add(numbers[right]);
                        result.add(list);
                        left++;
                        right--;
                        //避免3绿贞、4加入重復的數(shù)
                        while (numbers[left] == numbers[left-1]) {
                            left++;
                        }
                        while (numbers[right] == numbers[right+1]) {
                            right--;
                        }
                    }
                }
             }
        }
        return result;
    }
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市橘原,隨后出現(xiàn)的幾起案子籍铁,更是在濱河造成了極大的恐慌涡上,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,946評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件拒名,死亡現(xiàn)場離奇詭異吩愧,居然都是意外死亡,警方通過查閱死者的電腦和手機增显,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,336評論 3 399
  • 文/潘曉璐 我一進店門雁佳,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人同云,你說我怎么就攤上這事甘穿。” “怎么了梢杭?”我有些...
    開封第一講書人閱讀 169,716評論 0 364
  • 文/不壞的土叔 我叫張陵温兼,是天一觀的道長。 經(jīng)常有香客問我武契,道長募判,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,222評論 1 300
  • 正文 為了忘掉前任咒唆,我火速辦了婚禮届垫,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘全释。我一直安慰自己装处,他們只是感情好,可當我...
    茶點故事閱讀 69,223評論 6 398
  • 文/花漫 我一把揭開白布浸船。 她就那樣靜靜地躺著妄迁,像睡著了一般。 火紅的嫁衣襯著肌膚如雪李命。 梳的紋絲不亂的頭發(fā)上登淘,一...
    開封第一講書人閱讀 52,807評論 1 314
  • 那天,我揣著相機與錄音封字,去河邊找鬼黔州。 笑死,一個胖子當著我的面吹牛阔籽,可吹牛的內(nèi)容都是我干的流妻。 我是一名探鬼主播,決...
    沈念sama閱讀 41,235評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼笆制,長吁一口氣:“原來是場噩夢啊……” “哼绅这!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起项贺,我...
    開封第一講書人閱讀 40,189評論 0 277
  • 序言:老撾萬榮一對情侶失蹤君躺,失蹤者是張志新(化名)和其女友劉穎峭判,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體棕叫,經(jīng)...
    沈念sama閱讀 46,712評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡林螃,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,775評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了俺泣。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片疗认。...
    茶點故事閱讀 40,926評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖伏钠,靈堂內(nèi)的尸體忽然破棺而出横漏,到底是詐尸還是另有隱情,我是刑警寧澤熟掂,帶...
    沈念sama閱讀 36,580評論 5 351
  • 正文 年R本政府宣布缎浇,位于F島的核電站,受9級特大地震影響赴肚,放射性物質(zhì)發(fā)生泄漏素跺。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,259評論 3 336
  • 文/蒙蒙 一誉券、第九天 我趴在偏房一處隱蔽的房頂上張望指厌。 院中可真熱鬧,春花似錦踊跟、人聲如沸踩验。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,750評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽箕憾。三九已至,卻和暖如春决帖,著一層夾襖步出監(jiān)牢的瞬間厕九,已是汗流浹背蓖捶。 一陣腳步聲響...
    開封第一講書人閱讀 33,867評論 1 274
  • 我被黑心中介騙來泰國打工地回, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人俊鱼。 一個月前我還...
    沈念sama閱讀 49,368評論 3 379
  • 正文 我出身青樓刻像,卻偏偏與公主長得像,于是被迫代替她去往敵國和親并闲。 傳聞我的和親對象是個殘疾皇子细睡,可洞房花燭夜當晚...
    茶點故事閱讀 45,930評論 2 361

推薦閱讀更多精彩內(nèi)容