剑指Offer之Java算法习题精讲链表与数组专项训练

class Solution {

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

         int [] a = {- 1 ,- 1 };

         for ( int i = 0 ;i<nums.length- 1 ;i++){

             for ( int j = i+ 1 ;j<nums.length;j++){

                 if (nums[i]+nums[j]==target){

                     a[ 0 ] = i;

                     a[ 1 ] = j;

                     return a;

                 }

             }

         }

         return a;

     }

}

class Solution {

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

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

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

             index.put(nums[i],i);

         }

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

             if (index.containsKey(target - nums[i])&&i!=index.get(target - nums[i])){

                 return new int []{i,index.get(target - nums[i])};

             }

         }

         return new int []{- 1 ,- 1 };

     }

}

class Solution {

     public List<List<Integer>> threeSum( int [] nums) {

         Arrays.sort(nums);

         return nSumTarget(nums, 3 , 0 , 0 );

     }

     public List<List<Integer>> nSumTarget( int [] nums, int n, int start, int target){

         int size = nums.length;

         List<List<Integer>> res = new ArrayList<>();

         if (n < 2 || size < n) return res;

         if (n == 2 ){

             int lo = start, hi = size - 1 ;

             while (lo < hi){

                 int left = nums[lo], right = nums[hi];

                 int sum = left + right;

                 if (sum < target){

                     while (lo < hi && nums[lo] == left) lo++;

                 } else if (sum > target){

                     while (lo < hi && nums[hi] == right) hi--;

                 } else {

                     List<Integer> list = new ArrayList<>();

                     list.add(nums[lo]);

                     list.add(nums[hi]);

                     res.add(list);

                     while (lo < hi && nums[lo] == left) lo++;

                     while (lo < hi && nums[hi] == right) hi--;

                 }

             }

         } else {

             for ( int i = start; i < size; i++){

                 List<List<Integer>> temp = nSumTarget(nums, n - 1 , i + 1 , target - nums[i]);

                 for (List<Integer> list : temp){

                     list.add(nums[i]);

                     res.add(list);

                 }

                 while (i < size - 1 && nums[i] == nums[i + 1 ]) i++;

             }

         }

         return res;

     }

}

class Solution {

     public List<List<Integer>> fourSum( int [] nums, int target) {

         Arrays.sort(nums);

         return nSumTarget(nums, 4 , 0 ,target);

     }

     public List<List<Integer>> nSumTarget( int [] nums, int n, int start, int target){

         int size = nums.length;

         List<List<Integer>> res = new ArrayList<>();

         if (n < 2 || size < n) return res;

         if (n == 2 ){

             int lo = start, hi = size - 1 ;

             while (lo < hi){

                 int left = nums[lo], right = nums[hi];

                 int sum = left + right;

                 if (sum < target){

                     while (lo < hi && nums[lo] == left) lo++;

                 } else if (sum > target){

                     while (lo < hi && nums[hi] == right) hi--;

                 } else {

                     List<Integer> list = new ArrayList<>();

                     list.add(nums[lo]);

                     list.add(nums[hi]);

                     res.add(list);

                     while (lo < hi && nums[lo] == left) lo++;

                     while (lo < hi && nums[hi] == right) hi--;

                 }

             }

         } else {

             for ( int i = start; i < size; i++){

                 List<List<Integer>> temp = nSumTarget(nums, n - 1 , i + 1 , target - nums[i]);

                 for (List<Integer> list : temp){

                     list.add(nums[i]);

                     res.add(list);

                 }

                 while (i < size - 1 && nums[i] == nums[i + 1 ]) i++;

             }

         }

         return res;

     }   

}

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode() {}

  *     ListNode(int val) { this.val = val; }

  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

  * }

  */

class Solution {

     public ListNode reverseList(ListNode head) {

         if (head== null ||head.next== null ){

             return head;

         }

         ListNode last = reverseList(head.next);

         head.next.next = head;

         head.next = null ;

         return last;

     }

}

/**

  * Definition for singly-linked list.

  * public class ListNode {

  *     int val;

  *     ListNode next;

  *     ListNode() {}

  *     ListNode(int val) { this.val = val; }

  *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

  * }

  */

class Solution {

     ListNode cure = null ;

     public ListNode reverseBetween(ListNode head, int left, int right) {

         if (left== 1 ){

             return reverseN(head, right);

         }

         head.next = reverseBetween(head.next,left- 1 ,right- 1 );

         return head;

     }

     public ListNode reverseN(ListNode head, int n){

         if (n== 1 ){

             cure = head.next;

             return head;

         }

         ListNode last = reverseN(head.next,n- 1 );

         head.next.next = head;

         head.next = cure;

         return last;

     }

}