167. 两数之和 II - 输入有序数组
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public int[] twoSum(int[] numbers, int target) { int i=0; int j=numbers.length-1; while(i<j){ if(target>numbers[i]+numbers[j]) i++; else if(target<numbers[i]+numbers[j]) j--; else return new int[]{i+1,j+1}; } return new int[0]; } }
|
以上是一有序数组 若为无序数组 那么双指针无效 请看下题
1. 两数之和
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>(); for(int i = 0; i<nums.length; i++){ if(hashtable.containsKey(target-nums[i])){ return new int[]{hashtable.get(target-nums[i]),i}; } hashtable.put(nums[i],i); } return new int[0]; } }
|
633. 平方数之和
1 2 3 4 5 6 7 8 9 10 11 12
| class Solution { public boolean judgeSquareSum(int c) { long i=0; long j=(long)Math.sqrt(c); while(i<=j){ if(i*i+j*j==c) return true; if(i*i+j*j<c) i++; else j--; } return false; } }
|
680. 验证回文串
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { int del = 0; public boolean validPalindrome(String s) { int left=0,right=s.length()-1; while(left<right){ if(s.charAt(left)==s.charAt(right)) { left++; right--; } else{ if(del==0){ del++; return validPalindrome(s.substring(left,right)) || validPalindrome(s.substring(left+1,right+1)); } return false; } } return true; } }
|
substring(left,right) 左闭右开
String.charAt(i) 返回第i个字符
String.length() 返回字符串长度
88. 合并两个有序数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int p1=0,p2=0,p3=0; int[] nums3 = new int[m+n]; while(p1<m&&p2<n){ if(nums1[p1]<=nums2[p2]) nums3[p3++] = nums1[p1++]; else nums3[p3++] = nums2[p2++]; } if(p1<m){ while(p1<m){ nums3[p3++] = nums1[p1++]; } } if(p2<n){ while(p2<n){ nums3[p3++] = nums2[p2++]; } } for(int i=0;i<m+n;i++){ nums1[i] = nums3[i]; } } }
|
142. 环形链表 II
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
| public class Solution { public ListNode detectCycle(ListNode head) { ListNode fast,slow; fast = slow = head; while(fast!=null&&fast.next!=null){ fast = fast.next.next; slow = slow.next; if(slow == fast) break; } if(fast == null || fast.next == null) return null; slow = head; while(fast!=slow){ fast=fast.next; slow=slow.next; } return slow; } }
|

1679. K 和数对的最大数目
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
| class Solution { public int maxOperations(int[] nums, int k) { Arrays.sort(nums); int end = nums.length-1; int start = 0; int count = 0; while(start<end){ int sum = nums[start]+nums[end]; if(sum>k) end--; else if (sum<k) start++; else { end--; start++; count++; } } return count; } }
|
392. 判断子序列
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
| class Solution { public boolean isSubsequence(String s, String t) { if(s.equals("")) return true; int len1 = s.length(); int len2 = t.length(); int count=0; int i=0,j=0; while(i<len1&&j<len2) if(s.charAt(i)==t.charAt(j)){ i++; j++; count++; if(count==len1) return true; }else{ j++; } return false;
} }
|
11. 盛最多水的容器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public int maxArea(int[] height) { int maxm = 0; int start = 0; int end = height.length-1; int chang = height.length-1; while(start < end){ int kuan = Math.min(height[start],height[end]); if(maxm<chang*kuan){ maxm = chang*kuan; } if(height[start]<height[end]) { start++; chang--; }else{ end--; chang--; } } return maxm;
} }
|
⭐ left左边都是非零的 right持续向前移动 遇见非0就swap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| class Solution { public void moveZeroes(int[] nums) { int left = 0; int right =0; while(right<nums.length){ if(nums[right]!=0){ int temp = nums[left]; nums[left] = nums[right]; nums[right]=temp; left++; } right++; } } }
|
27. 移除元素
⭐ 同上题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41
| class Solution { public int removeElement(int[] nums, int val) { int left =0 ,right =0; int len = nums.length; int count=0; while(right<len){ if(nums[right]!=val){ nums[left]=nums[right]; left++; count++; } right++; } return count; } }
class Solution { public int removeElement(int[] nums, int val) { int left = 0; int right =0; int count=0; while(right<nums.length){ if(nums[right]!=val){ int temp = nums[left]; nums[left] = nums[right]; nums[right]=temp; left++; count++; } right++; } return count; } }
|