two sum 3題

I非整列,最速O(n),hashmapで解決
 

public class Solution {

    public int[] twoSum(int[] numbers, int target) {

        int[] res  =  new int[2];

        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

        if(numbers==null || numbers.length<2) return res;

        

        for(int i=0; i<numbers.length; i++){

            if(!hm.containsKey(target-numbers[i])){

                hm.put(numbers[i], i);

            }else{

                res[0] = hm.get(target-numbers[i])+1;

                res[1] = i+1;

                break;

            }

        }

       return res;

    }

}

 
 
 
II配列配列配列,2 pointers解決
 

public class Solution {

    public int[] twoSum(int[] numbers, int target) {

        int[] res  =  new int[2];

        int sum = 0, low =0, high = numbers.length-1;

        if(numbers==null || numbers.length<2) return res;

        

       while(low<high){

           sum = numbers[low]+numbers[high];

           if(sum==target){

               res[0] = low+1;

               res[1] = high+1;

               break;

           }else if(sum>target){

               high--;

           }else

                low++;

       }

       return res;

    }

}

 
III
 
 

Two Sum III - Data structure design (LeetCode HashMap)

 
Question:  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.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
 
 
注意target=2 elements in setがどのように判断するかはrefを参照してください.http://shanjiaxin.blogspot.com/2015/01/two-sum-iii-data-structure-design.html
 
copyそのcode:
 

import java.util.HashMap;

import java.util.Map;



// case: add(0) -> find(0) -> should be false

public class TwoSumIII {

    Map<Integer, Integer> dict = new HashMap<Integer, Integer>();

    

    public void add(int number) {

        if (dict.containsKey(number)) {

            dict.put(number, dict.get(number) + 1);

        } else {

            dict.put(number, 1);

        }

    }



    public boolean find(int value) {

        for (Integer key : dict.keySet()) {

        <span style="color:#ff0000;">    if (value - key == key) {

                if (dict.get(key) >= 2) {

                    return true;

                </span>}

            } else if (dict.containsKey(value - key)) {

                return true;

            }

        }

    

        return false;

    }

    

    public static void main(String[] args) {

        TwoSumIII util = new TwoSumIII();

        util.add(1);

        util.add(3);

        util.add(5);

        

        System.out.println(util.find(4));

        System.out.println(util.find(7));

    }

    

}