LeetCode(69) -- 18, 19

P18. 4Sum (Medium)

My Solution

public class P18_4Sum {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                int l = j + 1;
                int r = nums.length - 1;
                while (l < r) {
                    if (nums[i] + nums[j] + nums[l] + nums[r] == target) {
                        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
                        res.add(list);
                        l++;
                        r--;
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++;
                        }
                        while (l < r && nums[r] == nums[r + 1]) {
                            r--;
                        }
                    } else if (nums[i] + nums[j] + nums[l] + nums[r] < target) {
                        l++;
                        while (l < r && nums[l] == nums[l - 1]) {
                            l++;
                        }
                    } else {
                        r--;
                        while (l < r && nums[r] == nums[r + 1]) {
                            r--;
                        }
                    }
                }
                while (j + 1 < nums.length - 2 && nums[j + 1] == nums[j]) {
                    j++;
                }
            }
            while (i + 1 < nums.length - 3 && nums[i + 1] == nums[i]) {
                i++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = new P18_4Sum().fourSum(new int[]{-1, -5, -5, -3, 2, 5, 0, 4}, -7);
        System.out.println("lists = " + lists);
    }
}

The Best Solution

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
		ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
		int len = nums.length;
		if (nums == null || len < 4)
			return res;

		Arrays.sort(nums);

		int max = nums[len - 1];
		if (4 * nums[0] > target || 4 * max < target)
			return res;

		int i, z;
		for (i = 0; i < len; i++) {
			z = nums[i];
			if (i > 0 && z == nums[i - 1])// avoid duplicate
				continue;
			if (z + 3 * max < target) // z is too small
				continue;
			if (4 * z > target) // z is too large
				break;
			if (4 * z == target) { // z is the boundary
				if (i + 3 < len && nums[i + 3] == z)
					res.add(Arrays.asList(z, z, z, z));
				break;
			}

			threeSumForFourSum(nums, target - z, i + 1, len - 1, res, z);
		}

		return res;
	}

    public void threeSumForFourSum(int[] nums, int target, int low, int high, ArrayList<List<Integer>> fourSumList,
			int z1) {
		if (low + 1 >= high)
			return;

		int max = nums[high];
		if (3 * nums[low] > target || 3 * max < target)
			return;

		int i, z;
		for (i = low; i < high - 1; i++) {
			z = nums[i];
			if (i > low && z == nums[i - 1]) // avoid duplicate
				continue;
			if (z + 2 * max < target) // z is too small
				continue;

			if (3 * z > target) // z is too large
				break;

			if (3 * z == target) { // z is the boundary
				if (i + 1 < high && nums[i + 2] == z)
					fourSumList.add(Arrays.asList(z1, z, z, z));
				break;
			}

			twoSumForFourSum(nums, target - z, i + 1, high, fourSumList, z1, z);
		}

	}


    private void twoSumForFourSum(int[] nums,int target,int low,int high,List<List<Integer>> result,int z1,int z2){

        if(low>=high) return;
        int max = nums[high];
        if(2*nums[low]>target||2*max<target){
            return;
        }

        int i=low;
        int j=high;
        int sum ;

        while (i<j){
            sum = nums[i]+nums[j];
            if(sum==target){
                result.add(Arrays.asList(z1,z2,nums[i],nums[j]));
                i++;
                j--;
                while(i<j&&nums[i]==nums[i-1]) i++;
                while (i<j&&nums[j]==nums[j+1]) j--;

            }else if(sum<target){
                i++;
            }else{
                j--;
            }
        }
    }
}

P19. Remove Nth Node From End of List (Medium)

Given a linked list, remove the n-th node from the end of list and return its head.

My Solution

public class P19_RemoveNthNodeFromEndofList {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode detector = head;
        for (int i = 0; i < n; i++) {
            detector = detector.next;
        }
        if (detector == null) {
            return head.next;
        }
        ListNode curr = head;
        while (detector.next != null) {
            curr = curr.next;
            detector = detector.next;
        }
        curr.next = curr.next.next;
        return head;
    }
}

100%