算法|双指针、滑动窗口
2023-01-12 本文已影响0人
激扬飞雪
11. 盛最多水的容器
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right){
int area = (right - left) * Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, area);
if (height[left] > height[right]) right--;
else left++;
}
return maxArea;
}
}
15. 三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int i = 0;
int length = nums.length;
while (i < length){
if (i != 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
int left = i + 1;
int right = length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
i++;
}
return result;
}
}
16. 最接近的三数之和
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int i = 0;
int length = nums.length;
int bestSum = Integer.MAX_VALUE;
while (i < length) {
if (i != 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
int left = i + 1;
int right = length - 1;
while (left < right){
int sum = nums[i] + nums[left] + nums[right];
if (sum == target) return target;
else if (sum > target) right--;
else left++;
if (Math.abs(sum - target) < Math.abs(bestSum - target)) {
bestSum = sum;
}
}
i++;
}
return bestSum;
}
}
18. 四数之和
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int i = 0;
int length = nums.length;
while (i < length){
if (i != 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
int j = i + 1;
while (j < length){
if (j != i + 1 && nums[j] == nums[j - 1]) {
j++;
continue;
}
int left = j + 1;
int right = length - 1;
// System.out.println(i + " " + j);
while (left < right){
long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
System.out.println("*****************");
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
j++;
}
i++;
}
return result;
}
}
680. 验证回文串 II
class Solution {
private boolean isVaild(String s, int left, int right) {
while (left < right){
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return isVaild(s, left + 1, right) || isVaild(s, left, right - 1);
}
left++;
right--;
}
return true;
}
}
26. 删除有序数组中的重复项
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;
for (int j = 1; j < nums.length; j++){
if (nums[j] != nums[i]) {
nums[++i] = nums[j];
}
}
return i + 1;
}
}
75. 颜色分类
class Solution {
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public void sortColors(int[] nums) {
int i = 0;
int length = nums.length;
int lt = -1;
int gt = length;
while (i < gt){
if (nums[i] == 1) {
i++;
} else if (nums[i] == 0) {
lt++;
swap(nums, i, lt);
i++;
} else {
gt--;
swap(nums, i, gt);
}
}
}
}
240. 搜索二维矩阵 II
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
int n = matrix[0].length;
int j = n - 1;
int i = 0;
while (j >= 0 && i < m){
if (matrix[i][j] > target) {
j--;
} else if (matrix[i][j] < target) {
i++;
} else {
return true;
}
}
return false;
}
}
3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
if (s == null || s.length() == 0) return 0;
HashSet<Character> hashSet = new HashSet<>();
int j = 0;
int maxLength = 0;
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
while (hashSet.contains(c)){
hashSet.remove(s.charAt(j++));
}
hashSet.add(c);
maxLength = Math.max(maxLength, i - j + 1);
}
return maxLength;
}
}
28. 找出字符串中第一个匹配项的下标
class Solution {
public int strStr(String haystack, String needle) {
if (needle.length() > haystack.length()) return -1;
int length1 = haystack.length();
int length2 = needle.length();
int i = 0;
int j = 0;
while (i < length1) {
char h = haystack.charAt(i);
char n = needle.charAt(j);
// System.out.println(h + " " + n);
if (h == n) {
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
if (j == length2) {
return i - j;
}
}
return -1;
}
}
76. 最小覆盖子串
class Solution {
public String minWindow(String s, String t) {
HashMap<Character, Integer> tHashMap = new HashMap<>();
for (int i = 0; i < t.length(); i++){
tHashMap.put(t.charAt(i), tHashMap.getOrDefault(t.charAt(i), 0) + 1);
}
int count = 0;
int j = 0;
int left = 0;
int minLength = Integer.MAX_VALUE;
HashMap<Character, Integer> sHashMap = new HashMap<>();
for (int i = 0; i < s.length(); i++){
char c = s.charAt(i);
sHashMap.put(c, sHashMap.getOrDefault(c, 0) + 1);
if (sHashMap.get(c).equals(tHashMap.getOrDefault(c, 0))) count++;
//达到符合t的字符串
if (count == tHashMap.size()) {
//缩小窗口的范围
while (count == tHashMap.size()) {
int len = i - j + 1;
if (minLength > len) {
minLength = len;
left = j;
}
char cc = s.charAt(j);
if (sHashMap.get(cc).equals(tHashMap.getOrDefault(cc, 0))) count--;
sHashMap.put(cc, sHashMap.get(cc) - 1);
j++;
}
}
}
return minLength == Integer.MAX_VALUE ? "" : s.substring(left, left + minLength);
}
}
209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int j = 0;
int minLength = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++){
sum += nums[i];
while (sum >= target){
minLength = Math.min(minLength, i - j + 1);
sum -= nums[j++];
}
}
return minLength == Integer.MAX_VALUE ? 0 : minLength;
}
}
1004. 最大连续1的个数 III
class Solution {
public int longestOnes(int[] nums, int k) {
int j = 0;
int maxCount = Integer.MIN_VALUE;
for (int i = 0; i < nums.length; i++){
if (nums[i] == 0) k--;
while (k < 0) {
if (nums[j] == 0) k++;
j++;
}
maxCount = Math.max(maxCount, i - j + 1);
}
return maxCount == Integer.MIN_VALUE ? 0 : maxCount;
}
}
