写一个查找表和数组的算法
查找有无一般使用set数据结构
查找对应关系使用Map映射数据结构
给定两个数组nums1=[1，2，2，1] num2=[2，2]求两个数组的公共元素 结果为[2]
将一个集合中的元素存入set集合中，然后从另一个集合中取出元素判断在不在原来的set集合中，如果在则存
入另一个set集合。
public int[] intersection(int[] nums1, int[] nums2) {
TreeSet<Integer> record = new TreeSet<Integer>();
for(int num: nums1)
record.add(num);
TreeSet<Integer> resultSet = new TreeSet<Integer>();
for(int num: nums2)
if(record.contains(num))
resultSet.add(num);
int[] res = new int[resultSet.size()];
int index = 0;
for(Integer num: resultSet)
res[index++] = num;
return res;
}给定两个数组nums1=[1，2，2，1] num2=[2，2]求两个数组的交集 结果为[2，2]
与上一道题不同的地方在于记录每一个数组的元素也要记录出现的次数，次数也有意义，典型的键值对应的问题。
public int[] intersect(int[] nums1, int[] nums2) {
//HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
TreeMap<Integer, Integer> record = new TreeMap<Integer, Integer>();
for(int num: nums1)
if(!record.containsKey(num))
record.put(num, 1);
else
record.put(num, record.get(num) + 1);
ArrayList<Integer> result = new ArrayList<Integer>();
for(int num: nums2)
if(record.containsKey(num) && record.get(num) > 0){
result.add(num);
record.put(num, record.get(num) - 1);
}
int[] ret = new int[result.size()];
int index = 0;
for(Integer num: result)
ret[index++] = num;
return ret;
}给定一个整形数组nums，返回两个索引值等于给定的target值
HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
for(int i = 0 ; i < nums.length; i ++){
int complement = target - nums[i];
if(record.containsKey(complement)){
int[] res = {i, record.get(complement)};
return res;
}
record.put(nums[i], i);
}
HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
for(int i = 0 ; i < nums.length ; i ++)
record.put(nums[i], i);
for(int i = 0 ; i < nums.length; i ++){
Integer index = record.get(target - nums[i]);
if(index != null && index != i){
int[] res = {i, index};
return res;
}
}
给定四个整形数组A\B\C\D，A\B\C\D均含有相同的元素个数N，寻找多少个i,j,k,l的组合，使得A[i]+B[j]+C[k]+D[l] == 0，
和有可能重复，如果暴力解发n^4效率不够，可以降低复杂度为n^2
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
if(A == null || B == null || C == null || D == null)
throw new IllegalArgumentException("Illegal argument");
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0 ; i < C.length ; i ++)
for(int j = 0 ; j < D.length ; j ++){
int sum = C[i] + D[j];
if(map.containsKey(sum))
map.put(sum, map.get(sum) + 1);
else
map.put(sum, 1);
}
int res = 0;
for(int i = 0 ; i < A.length ; i ++)
for(int j = 0 ; j < B.length ; j ++)
if(map.containsKey(-A[i]-B[j]))
res += map.get(-A[i]-B[j]);
return res;
}public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
if(A == null || B == null || C == null || D == null)
throw new IllegalArgumentException("Illegal argument");
HashMap<Integer, Integer> mapAB = new HashMap<Integer, Integer>();
for(int i = 0 ; i < A.length ; i ++)
for(int j = 0 ; j < B.length ; j ++){
int sum = A[i] + B[j];
if(mapAB.containsKey(sum))
mapAB.put(sum, mapAB.get(sum) + 1);
else
mapAB.put(sum, 1);
}
HashMap<Integer, Integer> mapCD = new HashMap<Integer, Integer>();
for(int i = 0 ; i < C.length ; i ++)
for(int j = 0 ; j < D.length ; j ++){
int sum = C[i] + D[j];
if(mapCD.containsKey(sum))
mapCD.put(sum, mapCD.get(sum) + 1);
else
mapCD.put(sum, 1);
}
int res = 0;
for(Integer sumab: mapAB.keySet()){
if(mapCD.containsKey(-sumab))
res += mapAB.get(sumab) * mapCD.get(-sumab);
}
return res;
}给定平面上的n个点，存在多少条路径由这些点构成的三元组使得i，j两点的距离等于i，k两点的距离。‘
查找表的键是距离，值是有几个这样的点
public int numberOfBoomerangs(int[][] points) {
int res = 0;
for( int i = 0 ; i < points.length ; i ++ ){
// record中存储 点i 到所有其他点的距离出现的频次
HashMap<Integer, Integer> record = new HashMap<Integer, Integer>();
for(int j = 0 ; j < points.length ; j ++)
if(j != i){
// 计算距离时不进行开根运算, 以保证精度
int dis = dis(points[i], points[j]);
if(record.containsKey(dis))
record.put(dis, record.get(dis) + 1);
else
record.put(dis, 1);
}
for(Integer dis: record.keySet())
res += record.get(dis) * (record.get(dis) - 1);
}
return res;
}
private int dis(int[] pa, int pb[]){
return (pa[0] - pb[0]) * (pa[0] - pb[0]) +
(pa[1] - pb[1]) * (pa[1] - pb[1]);
}给定一个整形数组nums和一个整数k，是否存在索引i和j使得nums[i]==nums[j]，且i和j之间的差不超过k
滑动窗口思路，因为nums[i]-nums[j]<=k，他们一定在一个区间内，区间长度为k+1
如果没有找到，l+1继续寻找
整个过程如果还没有找到则l+k+1，一直保持有k+1长度的区间，一个一个元素的滑动每次都有个新的元素满足要求，重复
public boolean containsNearbyDuplicate(int[] nums, int k) {
if(nums == null || nums.length <= 1)
return false;
if(k <= 0)
return false;
HashSet<Integer> record = new HashSet<Integer>();
for(int i = 0 ; i < nums.length; i ++){
if(record.contains(nums[i]))
return true;
record.add(nums[i]);
if(record.size() == k + 1)
record.remove(nums[i-k]);
}
return false;
}给定一个整形数组nums和一个整数k，是否存在索引i和j使得nums[i]和nums[j]之间的差别不超过给定的整数t，且i和j之间的差不超过k
与上面不同，当前元素v与x的绝对值小于t，元素的范围在v-t到v+t之间，要求存的数据有顺序性
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
// 这个问题的测试数据在使用int进行加减运算时会溢出
// 所以使用long long
TreeSet<Long> record = new TreeSet<Long>();
for(int i = 0 ; i < nums.length ; i ++){
if(record.ceiling((long)nums[i] - (long)t) != null &&
record.ceiling((long)nums[i] - (long)t) <= (long)nums[i] + (long)t)
return true;
record.add((long)nums[i]);
if(record.size() == k + 1)
record.remove((long)nums[i-k]);
}
return false;
}给定一个数组将数组中的所有0元素放在末尾，维持其他所有非0的元素相对位置
ArrayList<Integer> nonZeroElements = new ArrayList<Integer>();
// 将vec中所有非0元素放入nonZeroElements中
for(int i = 0 ; i < nums.length ; i ++)
if(nums[i] != 0)
nonZeroElements.add(nums[i]);
// 将nonZeroElements中的所有元素依次放入到nums开始的位置
for(int i = 0 ; i < nonZeroElements.size() ; i ++)
nums[i] = nonZeroElements.get(i);
// 将nums剩余的位置放置为0
for(int i = nonZeroElements.size() ; i < nums.length ; i ++)
nums[i] = 0;
不开辟辅助数组，如果遇到非零的元素放在前面
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
for(int i = 0 ; i < nums.length ; i ++)
if( nums[i] != 0 )
nums[k++] = nums[i];
// 将nums剩余的位置放置为0
for(int i = k ; i < nums.length ; i ++)
nums[i] = 0;
}
使用两个指针对非零元素与零元素交换位置
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
// 同时, [k...i] 为 0
for(int i = 0 ; i < nums.length ; i ++)
if(nums[i] != 0)
swap(nums, k++, i);
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
如果整个数组都是非零元素，会出现自己和自己交换元素的情况，还可以加一个判断
public void moveZeroes(int[] nums) {
int k = 0; // nums中, [0...k)的元素均为非0元素
// 遍历到第i个元素后,保证[0...i]中所有非0元素
// 都按照顺序排列在[0...k)中
// 同时, [k...i] 为 0
for(int i = 0 ; i < nums.length ; i ++)
if(nums[i] != 0)
if(k != i)
swap(nums, k++, i);
else
k ++;
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}二分搜索在[l和r]范围内寻找target
[l...r]前后范围为闭区间内寻找target，下面的代码也要满足l和r的定义
l<=r边界问题，因为arr[mid]不是要找的值，所以l=mid+1
public static int binarySearch(Comparable[] arr, int n, Comparable target){
int l = 0, r = n - 1; // 在[l...r]的范围里寻找target
while(l <= r){ // 当 l == r时,区间[l...r]依然是有效的
int mid = l + (r - l) / 2;
if(arr[mid].compareTo(target) == 0) return mid;
if(target.compareTo(arr[mid]) > 0)
l = mid + 1; // target在[mid+1...r]中; [l...mid]一定没有target
else // target < arr[mid]
r = mid - 1; // target在[l...mid-1]中; [mid...r]一定没有target
}
return -1;
}如果设置初始值为n，r的意义发生了变化，在[l,r)才有意义。
因为是开区间arr[mid]不包含在区间内
public static int binarySearch(Comparable[] arr, int n, Comparable target){
int l = 0, r = n; // 在[l...r)的范围里寻找target
while(l < r){ // 当 l == r 时, 区间[l...r)是一个无效区间
int mid = l + (r - l) / 2;
if(arr[mid].compareTo(target) == 0) return mid;
if(target.compareTo(arr[mid]) > 0)
l = mid + 1; // target在[mid+1...r)中; [l...mid]一定没有target
else // target < arr[mid]
r = mid; // target在[l...mid)中; [mid...r)一定没有target
}
return -1;
}n个元素的数组，数组的取值只有0，1，2三种可能，为数组排序。
public void sortColors(int[] nums) {
int[] count = {0, 0, 0}; // 存放0, 1, 2三个元素的频率
for(int i = 0 ; i < nums.length ; i ++){
assert nums[i] >= 0 && nums[i] <= 2;
count[nums[i]] ++;
}
int index = 0;
for(int i = 0 ; i < count[0] ; i ++)
nums[index++] = 0;
for(int i = 0 ; i < count[1] ; i ++)
nums[index++] = 1;
for(int i = 0 ; i < count[2] ; i ++)
nums[index++] = 2;
}三路快速排序的思路
0处在开始的位置，2处于末尾的位置，添加一个元素使得数组维持性质
public void sortColors(int[] nums) {
int zero = -1; // [0...zero] == 0
int two = nums.length; // [two...n-1] == 2
for(int i = 0 ; i < two ; ){
if(nums[i] == 1)
i ++;
else if (nums[i] == 2)
swap(nums, i, --two);
else{ // nums[i] == 0
assert nums[i] == 0;
swap(nums, ++zero, i++);
}
}
}
private void swap(int[] nums, int i, int j){
int t = nums[i];
nums[i]= nums[j];
nums[j] = t;
}给定一个整形数组和一个整数target，在其中寻找两个元素使其和尾target，返回两个数的索引
public int[] twoSum(int[] numbers, int target) {
if(numbers.length < 2 /*|| !isSorted(numbers)*/)
throw new IllegalArgumentException("Illegal argument numbers");
for(int i = 0 ; i < numbers.length ; i ++)
for(int j = i+1 ; j < numbers.length ; j ++)
if(numbers[i] + numbers[j] == target){
int[] res = {i+1, j+1};
return res;
}
throw new IllegalStateException("The input has no solution");
}提升效率，二分搜索法
public int[] twoSum(int[] numbers, int target) {
if(numbers.length < 2 /*|| !isSorted(numbers)*/)
throw new IllegalArgumentException("Illegal argument numbers");
for(int i = 0 ; i < numbers.length - 1 ; i ++){
int j = binarySearch(numbers, i+1, numbers.length-1, target - numbers[i]);
if(j != -1){
int[] res = {i+1, j+1};
return res;
}
}
throw new IllegalStateException("The input has no solution");
}
private int binarySearch(int[] nums, int l, int r, int target){
if(l < 0 || l > nums.length)
throw new IllegalArgumentException("l is out of bound");
if(r < 0 || r > nums.length)
throw new IllegalArgumentException("r is out of bound");
while(l <= r){
int mid = l + (r - l)/2;
if(nums[mid] == target)
return mid;
if(target > nums[mid])
l = mid + 1;
else
r = mid - 1;
}
return -1;
}去找小一个或大一个或位置的元素
public int[] twoSum(int[] numbers, int target) {
if(numbers.length < 2 /*|| !isSorted(numbers)*/)
throw new IllegalArgumentException("Illegal argument numbers");
int l = 0, r = numbers.length - 1;
while(l < r){
if(numbers[l] + numbers[r] == target){
int[] res = {l+1, r+1};
return res;
}
else if(numbers[l] + numbers[r] < target)
l ++;
else // numbers[l] + numbers[r] > target
r --;
}
throw new IllegalStateException("The input has no solution");
}
private boolean isSorted(int[] numbers){
for(int i = 1 ; i < numbers.length ; i ++)
if(numbers[i] < numbers[i-1])
return false;
return true;
}给定一个整形数组和一个数字s，寻找数组中最短的一个连续子数组，使得联塑子数组的和大于s
双重循环遍历i和j，求所有的连续
public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
int res = nums.length + 1;
for(int l = 0 ; l < nums.length ; l ++)
for(int r = l ; r < nums.length ; r ++){
int sum = 0;
for(int i = l ; i <= r ; i ++)
sum += nums[i];
if(sum >= s)
res = Math.min(res, r - l + 1);
}
if(res == nums.length + 1)
return 0;
return res;
}public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
// sums[i]存放nums[0...i-1]的和
int[] sums = new int[nums.length + 1];
sums[0] = 0;
for(int i = 1 ; i <= nums.length ; i ++)
sums[i] = sums[i-1] + nums[i-1];
int res = nums.length + 1;
for(int l = 0 ; l < nums.length ; l ++)
for(int r = l ; r < nums.length ; r ++){
// 使用sums[r+1] - sums[l] 快速获得nums[l...r]的和
if(sums[r+1] - sums[l] >= s)
res = Math.min(res, r - l + 1);
}
if(res == nums.length + 1)
return 0;
return res;
}暴力解包含了大量的重复计算
使用滑动窗口，如果和不为的话从j的一端增加一位，直到找到和大于s，然后从i的一端增加一位。
i小到一定程度总体小于s，这时候j再++
public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
int l = 0 , r = -1; // nums[l...r]为我们的滑动窗口
int sum = 0;
int res = nums.length + 1;
while(l < nums.length){ // 窗口的左边界在数组范围内,则循环继续
if(r + 1 < nums.length && sum < s)
sum += nums[++r];
else // r已经到头 或者 sum >= s
sum -= nums[l++];
if(sum >= s)
res = Math.min(res, r - l + 1);
}
if(res == nums.length + 1)
return 0;
return res;
}二分搜索法
public int minSubArrayLen(int s, int[] nums) {
if(s <= 0 || nums == null)
throw new IllegalArgumentException("Illigal Arguments");
// sums[i]存放nums[0...i-1]的和
int[] sums = new int[nums.length + 1];
sums[0] = 0;
for(int i = 1 ; i <= nums.length ; i ++)
sums[i] = sums[i-1] + nums[i-1];
int res = nums.length + 1;
for(int l = 0 ; l < nums.length ; l ++){
// Java类库中没有内置的lowerBound方法，
// 我们需要自己实现一个基于二分搜索的lowerBound:)
int r = lowerBound(sums, sums[l] + s);
if(r != sums.length){
res = Math.min(res, r - l);
}
}
if(res == nums.length + 1)
return 0;
return res;
}
// 在有序数组nums中寻找大于等于target的最小值
// 如果没有（nums数组中所有值都小于target），则返回nums.length
private int lowerBound(int[] nums, int target){
if(nums == null /*|| !isSorted(nums)*/)
throw new IllegalArgumentException("Illegal argument nums in lowerBound.");
int l = 0, r = nums.length; // 在nums[l...r)的范围里寻找解
while(l != r){
int mid = l + (r - l) / 2;
if(nums[mid] >= target)
r = mid;
else
l = mid + 1;
}
return l;
}
private boolean isSorted(int[] nums){
for(int i = 1 ; i < nums.length ; i ++)
if(nums[i] < nums[i-1])
return false;
return true;
}在一个字符串中寻找没有重复字母的最长子串
如“abcabcbb” 结果为"abc"
判断是否有重复的字母，freq有256个位置，freq[k]存ASCII码为k的元素
public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
// 整个循环从 l == 0; r == -1 这个空窗口开始
// 到l == s.size(); r == s.size()-1 这个空窗口截止
// 在每次循环里逐渐改变窗口, 维护freq, 并记录当前窗口中是否找到了一个新的最优值
while(l < s.length()){
if(r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
freq[s.charAt(++r)] ++;
else //r已经到头 || freq[s[r+1]] == 1
freq[s.charAt(l++)] --;
res = Math.max(res, r-l+1);
}
return res;
}改进r + 1 < s.length()
public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
while( r + 1 < s.length() ){
if( r + 1 < s.length() && freq[s.charAt(r+1)] == 0 )
freq[s.charAt(++r)] ++;
else //freq[s[r+1]] == 1
freq[s.charAt(l++)] --;
res = Math.max(res, r-l+1);
}
return res;
}public int lengthOfLongestSubstring(String s) {
int[] freq = new int[256];
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
while(r + 1 < s.length()){
while(r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
freq[s.charAt(++r)] ++;
res = Math.max(res, r - l + 1);
if(r + 1 < s.length()){
freq[s.charAt(++r)] ++;
assert(freq[s.charAt(r)] == 2);
while(l <= r && freq[s.charAt(r)] == 2)
freq[s.charAt(l++)] --;
}
}
return res;
}public int lengthOfLongestSubstring(String s) {
int[] last = new int[256];
Arrays.fill(last, -1);
int l = 0, r = -1; //滑动窗口为s[l...r]
int res = 0;
while(r + 1 < s.length()){
r ++;
if(last[s.charAt(r)] != -1)
l = Math.max(l, last[s.charAt(r)] + 1);
res = Math.max(res, r - l + 1);
last[s.charAt(r)] = r;
}
return res;
}
标签：return,nums,int,res,length,++,算法,查找,数组 From： https://blog.51cto.com/u_11837698/6082662