大家好,我是晴天学长,非常类似lc的两数之和,不过就是前期需要优化一下,找到技巧非常重要,需要的小伙伴可以关注支持一下哦!后续会继续更新的。💪💪💪
1) .矿石样本分析
2) .算法思路
1.首先预处理每个值的min(i+1,n-i)。
2.再遍历所有可能出现的x值。
3.t=max(f(x),f(t-x))
4.注意事项:排除x=k-x的情况
5.Java的list要用Arraylist,不然遍历会超时。
3).算法步骤
4). 代码实例
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
String[] s = in.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int k = Integer.parseInt(s[1]);
int[] a = new int[n];
Set<Integer>set = new HashSet<>();
s = in.readLine().split(" ");
for (int i = 0; i < n; i++) {
a[i] = Integer.parseInt(s[i]);
set.add(a[i]);
}
Map<Integer, Integer>map = new HashMap<>();
for (int i = 0; i < n; i++) {
int k1 = a[i];
if (!map.containsKey(k1)) {
map.put(k1, Math.min(i+1, n-i));
}
int k2 = Math.min(i+1, n-i);
if (k2<map.get(k1)) {
map.put(k1, k2);
}
}
int min = Integer.MAX_VALUE;
List<Integer> list = new ArrayList<>(map.keySet());
Map<Integer, Integer>map2 = new HashMap<>();
for (int i = 0; i < list.size(); i++) {
int x = list.get(i);
int y = k-x;
if (y!=x&&map2.containsKey(y)) {
min = Math.min(min, Math.max(map.get(x), map2.get(y)));
}
map2.put(x, map.get(x));
}
if (min==Integer.MAX_VALUE) {
System.out.println(-1);
}else {
System.out.println(min);
}
}
}
5). 总结
- 链表的时间复杂度要知道
查找
List list = new ArrayList<>();(o(1))
List list = new LinkedList<>();(o(n))
一般都用ArrayList,除非是修改