Share My Java Code using Map and two Pointers


  • 0
    L
    public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> quatreList=new LinkedList<List<Integer>>();
        HashMap<List<Integer>,Integer> map=new HashMap<List<Integer>,Integer>();
        
        Arrays.sort(num);
        
        for(int i=0;i<num.length;i++){
            if(i!=0 && num[i]==num[i-1])
                continue;
            List<List<Integer>> tripleList=new LinkedList<List<Integer>>();
            if(threeSum2Sides(num,i+1,target-num[i],tripleList)){
                for(List<Integer> triple : tripleList){
                    List<Integer>quatre=new LinkedList<Integer>();
                    quatre.add(num[i]);
                    quatre.addAll(triple);
                    if(!map.containsKey(quatre)){
                        map.put(quatre,i);
                        quatreList.add(quatre);
                    }
                }
            }
        }
        
        return quatreList;
    }
    
        //find the target from num[index]; for each index i, calculate from two sides
    	private boolean threeSum2Sides(int[] num, int index, int target,
    		List<List<Integer>> tripleList) {
    	HashMap<List<Integer>, Integer> map = new HashMap<List<Integer>, Integer>();
    	boolean flag = false;
    
    	for (int i = index; i < num.length - 2; i++) {
    		if (i != index && num[i] == num[i - 1])
    			continue;
    
    		int j = i + 1;
    		int k = num.length - 1;
    		while (j < k) {
    			if (num[i] + num[j] + num[k] == target) {
    				List<Integer> triple = new ArrayList<Integer>();
    				triple.add(num[i]);
    				triple.add(num[j]);
    				triple.add(num[k]);
    				if (!map.containsKey(triple)) {
    					map.put(triple, i);
    					tripleList.add(triple);
    					flag = true;
    				}
    			}
    			if (num[i] + num[j] + num[k] < target) {
    				j++;
    			} else {
    				k--;
    			}
    		}
    	}
    	return flag;
    }
    

    At first, i didnt use two pointers, just using hashMap like in 3Sum and 2Sum. but this case would try to iterate from front side of the array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.