Java 的 @FunctionalInterface 以及Lamda

背景

在使用MockMvc的时候我们通常会见到类似下面的表达

1
2
3
4
mockMvc.perform(MockMvcRequestBuilders.get("/some_api_endpoint")
.contentType(MediaType.APPLICATION_JSON))
.andExpect(status().isOk())
.andExpect(jsonPath("$[0].user_id").value("123"));

andExpect()到底是个什么东西?为什么里面传了函数之后返回结果还能继续调用自身?

经过翻阅文档我们发现,MockMvc.perform 返回一个ResultActions的instance。
而这个ResultActions则是一个接口。

1
2
3
4
5
6
7
8
9
public interface ResultActions {

ResultActions andExpect(ResultMatcher matcher) throws Exception;

ResultActions andDo(ResultHandler handler) throws Exception;

MvcResult andReturn();

}

这样就解释了为什么可以继续调用自身。

那么这个ResultMatcher是个什么东西?

1
2
3
4
5
6
7
8
9
10
11
@FunctionalInterface
public interface ResultMatcher {
void match(MvcResult result) throws Exception;
static ResultMatcher matchAll(ResultMatcher... matchers) {
return result -> {
for (ResultMatcher matcher : matchers) {
matcher.match(result);
}
};
}
}

于是引出了这个文章的最终话题,@FunctionalInterface到底是什么?

@FunctionalInterface和Java8 Lamda

其实理解了@FunctionalInterface对理解Lamda很有帮助,因为Lamda的本质是匿名函数。
@FunctionalInterface字如其名,是函数的接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Main {
@FunctionalInterface
interface FunctionPointer {
void helloWorld(String subject, String name);
}

private static void helloFromFunction(String subject, String name, FunctionPointer functionPointer){
functionPointer.helloWorld(subject, name);
}

private static void hello(String subject, String name){
System.out.println("Hello " + subject + ", I'm " + name + ". ");
}

public static void main(String[] args) {
helloFromFunction("world", "wrongwrong", (subject, name) -> System.out.println("Hello " + subject + ", I'm " + name + "."));
helloFromFunction("world", "wrongwrong", Main::hello);
}
}

上面的代码,我们用@FunctionalInterface标注了FunctionPointer, 于是任何我们定义的函数,只要符合其中定义的void helloWorld(string, string)的调用规则,都可以用FunctionPointer.helloWorld来调用。

概念上来说,一个@FunctionalInterface只能有一个抽象函数, 所以我们定义void hello(string, string)的时候并不需要声明我这个函数实现了FunctionPointer中的helloWorld这个方法。

甚至,我们只需在使用的时候带入一个匿名函数。

1
helloFromFunction("world", "wrongwrong", (subject, name) -> System.out.println("Hello " + subject + ", I'm " + name + "."));

这个就是Lamda的本质了。

PHP strtotime函数计算下个月时候的一个坑

我们用php获取下个月的月份的时候通常会想当然

1
echo date('Ym', strtotime('next month'));

平时看来并没有什么问题,但是当今天是1月31号的时候会发生什么呢?

1
2
3
4
5
6
7
8
9
10
11
<?php 
$date = "2018-01-31";

$ym1 = date('Y-m', strtotime('+1 month ' . $date));
$ym2 = date('Y-m', strtotime('+2 month ' . $date));
$ym3 = date('Y-m', strtotime('+3 month ' . $date));

var_dump($date);
var_dump($ym1);
var_dump($ym2);
var_dump($ym3);

我们期待的输出结果可能是

1
2
3
4
string(10) “2018-01-31”
string(7) “2018-02”
string(7) “2018-03”
string(7) “2018-04”

但是输出的结果确是

1
2
3
4
string(10) “2018-01-31”
string(7) “2018-03”
string(7) “2018-03”
string(7) “2018-05”

这到底是怎么会是呢?

原来,strtotime函数将1月31日的1个月以后计算成2月31日,显然,2月没有31日,于是,这个1个月后的时间就变成了相应的3月3日。去掉月份,于是得到了2018-03的结果。

那么要正确获取下个月的日期可以怎么做呢?

其实很简单。先取得这个月的第一天,然后再加上一个月就好了。

1
2
$date = date("Y-m-01");
$ym1 = date('Y-m', strtotime('+1 month ' . $date));
PHP

Spring Boot Redis Cluster的相关配置

搭建 Redis Cluster

直接使用docker创建一个Redis Cluster。

1
2
3
#docker-compose.yml
redisCluster:
image: grokzen/redis-cluster:3.2.13

这个Image默认将创建端口号从7000-7005的3Master3Slave的的Redis Cluster。

在SpringBoot的configuration中配置端口。

1
2
3
4
5
6
7
#application.properties
spring.redis.cluster.nodes[0]=notification_redis:7000
spring.redis.cluster.nodes[1]=notification_redis:7001
spring.redis.cluster.nodes[2]=notification_redis:7002
spring.redis.cluster.nodes[3]=notification_redis:7003
spring.redis.cluster.nodes[4]=notification_redis:7004
spring.redis.cluster.nodes[5]=notification_redis:7005

Java Configuration

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
@Data
@Configuration
@ConfigurationProperties(prefix = "spring.redis.cluster")
public class RedisClusterConf {

List<String> nodes;

@Bean
public RedisConnectionFactory connectionFactory() {
return new JedisConnectionFactory(new RedisClusterConfiguration(nodes));
}
@Bean
public RedisTemplate<String, MyObject> redisKvTemplate(@Qualifier("connectionFactory") RedisConnectionFactory factory){
RedisTemplate<String, Object> template = new RedisTemplate <>();
template.setConnectionFactory(factory);

Jackson2JsonRedisSerializer jackson2JsonRedisSerializer =new Jackson2JsonRedisSerializer<>(MyObject.class);

StringRedisSerializer stringRedisSerializer = new StringRedisSerializer();
template.setKeySerializer(stringRedisSerializer);
//template.setHashKeySerializer(stringRedisSerializer);
template.setValueSerializer(jackson2JsonRedisSerializer);
//template.setHashValueSerializer(jackson2JsonRedisSerializer);
return template;
}

}

public RedisTemplate<String, MyObject> redisKvTemplate(@Qualifier("connectionFactory") RedisConnectionFactory factory)
定义一个将MyObject对象序列化然后保存到Redis中的Template。

Spring-boot-starter-redis默认使用JdkSerializationRedisSerializer将value序列化(而Key则是默认使用StringRedisSerializer),
这样的结果就是我们直接在redis-cli中查看value的内容极其不方便。

具体可以参考这里

我们需要根据实际的需要,将Key和Value以肉眼可以理解的形式序列化。所以就有了

1
2
3
4
Jackson2JsonRedisSerializer jackson2JsonRedisSerializer =new Jackson2JsonRedisSerializer<>(MyObject.class);
StringRedisSerializer stringRedisSerializer = new StringRedisSerializer();
template.setKeySerializer(stringRedisSerializer);
template.setValueSerializer(jackson2JsonRedisSerializer);

这样,我们的Key直接以plain的String进行存储,Value被序列化成Json的String进行存储。

那么setHashKeySerializersetHashValueSerializer分别是什么呢?
原来是当value中包含HashMap的时候,我们需要将HashMap的Key和Value也进行序列化,
这个时候,我们也需要制定Key和Value的序列化方式。
在没有用到HashMap的情况下,我们自然就不需要指定了。

1
2
//template.setHashKeySerializer(stringRedisSerializer);
//template.setHashValueSerializer(jackson2JsonRedisSerializer);

另外参考

 

Spring Boot 使用RabbitMQ的实例

目标

Publisher将Json消息发送至RabbitMQ中,
Comsumer能够将RabbitMQ中的消息自动映射成对应的Java POJO。

准备

使用docker-compose迅速运行RabbitMQ。

1
2
3
4
5
rabbitmq:
image: rabbitmq:management
ports:
- "5672:5672"
- "15672:15672"

添加spring-boot-starter-amqp

1
2
3
4
5
6
7
dependencies {
implementation 'org.springframework.boot:spring-boot-starter-amqp'
testImplementation('org.springframework.boot:spring-boot-starter-test') {
exclude group: 'org.junit.vintage', module: 'junit-vintage-engine'
}
testImplementation 'org.springframework.amqp:spring-rabbit-test'
}

添加AMQP的Java Configuration。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
@EnableRabbit
public class AmqpConf implements RabbitListenerConfigurer {

@Bean
public MappingJackson2MessageConverter jackson2Converter() {
MappingJackson2MessageConverter converter = new MappingJackson2MessageConverter();
return converter;
}

@Bean
public DefaultMessageHandlerMethodFactory myHandlerMethodFactory() {
DefaultMessageHandlerMethodFactory factory = new DefaultMessageHandlerMethodFactory();
factory.setMessageConverter(jackson2Converter());
return factory;
}

@Override
public void configureRabbitListeners(RabbitListenerEndpointRegistrar registrar) {
registrar.setMessageHandlerMethodFactory(myHandlerMethodFactory());
}

}

添加Message Listener。

1
2
3
4
5
6
7
8
9
10
class Receiver {
@RabbitListener(queues = "queue")
public void receiveMessage(Foo foo) {
System.out.println("Received <" + foo.name + ">");
}
}

class Foo {
public String name;
}

解说

mappingJackson2MessageConverter能将接受到的Quque中的Message转换成对应的POJO。

Spring使用PayloadArgumentResolver去提取,转换Message为对应标记@RabbitListener Method中的Parameter。

我们需要自己实现一个RabbitListenerConfigurer,将Message converter设置成mappingJackson2MessageConverter。

具体参考这里

看不见的bom

背景

旁边的童鞋被QA的bug报告快搞疯了。
原因是,很简单的一个逻辑,parse一个csv,然后对比各个项目,其中,第一个项目是serviceId的flag,如果这个flag不是1,我们把db中对应的flag设置成true。
但是明明这么很简单的一个逻辑,csv中的flag也是1,但是跑了之后db中的flag却不是true。这是为啥?

看不见的BOM

排除其他可能性之后再次观察这个csv,发现出现问题的记录就只有第一条。而这个servideId的flag出现在第一个位置,也就是说?会不会有可能有看不见的字符导致我们parse到的flag并不是1?

经验告诉我们,windows的一些编辑器默认会在文本文件前面插入看不见的BOM字符。

那会不会真的是存在BOM字符呢?

vim下查看并排除BOM

1
2
3
4
:set bomb?

> bomb
> nobomb

因为bom总是出现在文本第一个字符,所以简单的只是显示了是否存在。

当我们想要去除BOM的时候。

1
:set nobomb

即可。

后话

折腾浪费的时间最终就是转换成了经验。
希望以后遇到类似问题反应更快一点吧。

vim

Swap Nodes in Pairs

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
[24] Swap Nodes in Pairs  

https://leetcode.com/problems/swap-nodes-in-pairs/description/

* algorithms
* Medium (45.98%)
* Total Accepted: 352.7K
* Total Submissions: 762.9K
* Testcase Example: '[1,2,3,4]'

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list's nodes, only nodes itself may be changed.

 

Example:


Given 1->2->3->4, you should return the list as 2->1->4->3.

思路

这道题如果试图去用一大堆指针指向需要交换的节点以及之后的节点,然后迭代就会被弄晕。
最后还是试图使用递归的方法解决。

我们把这个问题分割称两个部分,其实就是首先交换先头两个节点,然后,去交换剩下来的链表。

我们让lists中,第一个节点为head,第二个节点为tail。

最终得到的结果无非就是tail->head->swap_pairs(tail.next)

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val)
# @val = val
# @next = nil
# end
# end

# @param {ListNode} head
# @return {ListNode}
def swap_pairs(head)
return head if head == nil || head.next == nil
tail = head.next
left = tail.next
tail.next = head
head.next = swap_pairs(left)
return tail
end

反思

变量太多把自己搞晕的时候,想想是否有简介的递归可以利用。

Merge K Sorted List

题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
[23] Merge k Sorted Lists  

https://leetcode.com/problems/merge-k-sorted-lists/description/

* algorithms
* Hard (35.68%)
* Total Accepted: 444.4K
* Total Submissions: 1.2M
* Testcase Example: '[[1,4,5],[1,3,4],[2,6]]'

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:


Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

思路

我们已经有了merge-2-sorted-lists的解法,这道题只需迭代调用。

但是有个问题很关键,就是我们到底要合并多少次呢? 如果是每次把新的list合并到结果中,据说会超时。

这个时候的时间复杂度是2n + 3n + ... + kn = [(k+1)*k/2-1]*n = O(nk^2)

不过反正我用递归的话并没有超时。

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
42
43
44
45
46
47
48
49
50
51
52
53
def merge_k_lists(lists)
if lists.count == 0
return nil
end
if lists.count == 1
return lists[0]
end
if lists.count == 2
return merge_two_lists(lists[0], lists[1])
else
list = merge_k_lists(lists[1..-1])
return merge_two_lists(lists[0], list)
end
end

def merge_two_lists(l1, l2)
i = l1
j = l2
if l1 == nil
return l2 ? l2 : nil
elsif l2 == nil
return l1 ? l1 : nil
end
if l1.val > l2.val
head = l2
j = j.next
else
head = l1
i = i.next
end
current = head
while i && j
if i.val < j.val
current.next = i
i = i.next
else
current.next = j
j = j.next
end
current = current.next
end
while i
current.next = i
i = i.next
current = current.next
end
while j
current.next = j
j = j.next
current = current.next
end
return head
end

分治法解法

同样利用已经写好的merge-2-sorted-lists, 只不过这次通过两两合并来减少合并次数。
时间复杂度为时间复杂度为O(nk log(k))

最小堆排序解法

首先复习一下堆的概念。堆可以分为最小堆和最大堆。就最小堆来说,就是对于一棵二叉树,root节点总是保持最小。
任何父节点总是小于叶子节点。

最小堆主要有push和pop操作。

push: 将新元素插入到最后的叶子节点,并于父节点比较,如果小于父节点,则交换。如此循环直到遇到比自己小的父节点或者最后到root节点。

pop: 获取最小元素,由上往下比较左右两子节点,将子节点中较大的节点作为新的父节点,不断重复,直到叶子节点。

对于解决 merge-k-sorted-lists问题,我们可以先将k个list中的第一个元素组成一个堆。
每次取堆顶元素root,放入result中,然后把root.next插入到堆中。这样可以保证我们每次从堆顶获取的元素都是最小的。

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
class Solution {
public:
struct compNode {
bool operator()(ListNode *p, ListNode *q) const {
return p->val>q->val;
}
};

ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
ListNode *dummy = new ListNode(0), *tail = dummy;

for(int i=0; i<lists.size(); i++)
if(lists[i]) pq.push(lists[i]);

while(!pq.empty()) {
tail->next = pq.top();
tail = tail->next;
pq.pop();
if(tail->next) pq.push(tail->next);
}

return dummy->next;
}
};

反思

堆是一个陌生的数据结构。需要特别留意。

Generate Parentheses

题目

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
[22] Generate Parentheses  

https://leetcode.com/problems/generate-parentheses/description/

* algorithms
* Medium (56.57%)
* Total Accepted: 386.8K
* Total Submissions: 680.5K
* Testcase Example: '3'


Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.



For example, given n = 3, a solution set is:


[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]

错误的漩涡

乍看这个题目,决定用递归解决。自己思考了一下,大概就是假设已经有生成的generateParenthesis(n-1)的结果,然后我们对所有的结果进行组合,大概有

1
2
3
"("+generateParenthesis(n-1)+")"
"()"+generateParenthesis(n-1)
generateParenthesis(n-1)+"()"

的形式。然后组成一个递归,当n=1的时候返回["()"]

提交结果,大错特错。比如,当n=3的时候,我们怎么样都无法获得类似(()())的形式。

正确的思考方法

其实正确的思考方法,想得到就是想得到,想不到就是背下来。

  1. 当”(“数小于n的时候,可以继续添加”(“

  2. 当”)”的个数小于”(“的个数的时候,可以添加”)”

于是我们可以新建一个方法来记录当前的结果,以及左右括号的计数,然后进行递归。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# @param {Integer} n
# @return {String[]}
def generate_parenthesis(n)
stack = []
generate(n,0,0,"",stack)
return stack
end

def generate(n, left, right, current, stack)
if left == n && right == n
stack << current
end
if left < n
generate(n, left+1, right, current+"(", stack)
end
if right < left
generate(n, left, right+1, current+")", stack)
end
end

插曲

在翻看答案的时候,第一眼看到了下面的解答。

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
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> allComb;
string comb;
findParenthesis(n, 0, 0, comb, allComb);
return allComb;
}

void findParenthesis(int n, int nleft, int nright, string &comb, vector<string> &allComb) {
if(nleft==n && nright==n) {
allComb.push_back(comb);
return;
}

if(nleft<n) {
comb.push_back('(');
findParenthesis(n, nleft+1, nright, comb, allComb);
comb.pop_back();
}

if(nright<nleft) {
comb.push_back(')');
findParenthesis(n, nleft, nright+1, comb, allComb);
comb.pop_back();
}
}
};

然后我陷入了沉思,最后的comb.pop_back()是为什么?
对比正解,我们发现我们在递归的时候改变了重复带入的变量的值,所以在下一次迭代之前,应该把它恢复。
至于为什么要恢复。。。撒。

你也许不需要图床

背景

使用hexo写博客已经有三四年了。
最困扰的问题依然是上传需要插入的contents的问题。

上传图片方式演化

由于hexo只是个静态博客生成器,
并不像wordpress那样有强大的contents管理功能,所有的contents我们只能通过上传到某个地方然后引用。
很显然,第一个被pass的解决方案是把图传到公共的图床上去。比如新浪微博或者七牛云存储。
前者类似盗链行为,后者复杂的流量收费计算方式实在是让人头疼。

我们的目标是,把所有的图片都放置在自己拥有管理权的地方。

自己host的图床工具

这是最早使用的解决方案。首先在github上找了个docker封装好的图床web app。然后挂到服务器上。
总体来说没什么大问题。每30分钟我都会备份一下docker container里面的图片。

1
30 * * * * /usr/bin/docker cp b7ceed2898de003e02b0addee90d0d50c63d046cd422d17dc5ba9085d44ea237:/usr/share/nginx/html/upload /data/pictshareuploads/upload/

但是后来服务器运营商MAINT停机的时候,我的docker就挂了。之前的图片虽然有作备份,现存的图姑且是全部救了回来,就是container重启之后不知道为啥UI什么的全部发生了变化,我也再也没有权限上传图片了。

当然花时间理清楚思路固然重要,不过对于我只想要简简单单解决上传图片的目的来说,显然有些多余了。

于是我把眼光转向了吱呀呀转动着的挂在自己家的NAS。

自宅NAS的复杂繁琐

QNAP这个NAS服务器真的是非常良心。不但免费提供了DDNS绑定,各种定制的contents管理工具也是十分便捷。
唯一让人头疼的是,当我们要上传图片并获取公链的时候,步骤太过于复杂。

  1. 打开FileStation, 然后选择上传。

  1. 选择上传的文件之后,点击共享,然后勾选永久共享。

  1. 获取共享链接之后,在共享链接的界面点开图片,获取真正的链接。然后复制到剪贴板。

更要命的是由于手动步骤太多导致很多时候直接就是贴错了图。

痛定思痛,我决定花点时间来解决传图的问题。目标是使用最短的时间上传任意大小的图片,并且减少操作的失误。

NGINX + SCP

这个方法的思路是。

  1. 获取本地图片/视频的md5。

  2. 用scp将本地图片上传到自己服务器的公开目录上,并重命名成”md5+extension”的名称。

  3. 拼接出图片的url,自动复制到剪贴板。

事先准备nginx的公开目录。

我们建立一个alias,把新建的目录挂到wwww.bocchi.tokyo/upload的path下面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
server {
listen 443 http2;

ssl on;
server_name www.bocchi.tokyo;
ssl_certificate /etc/letsencrypt/live/www.bocchi.tokyo/fullchain.pem;
ssl_certificate_key /etc/letsencrypt/live/www.bocchi.tokyo/privkey.pem;
root /var/www/myblog;
index index.html;

location / {
add_header Cache-Control max-age=0;
add_header Cache-Control no-store;
add_header Pragma no-cache;
#rewrite ^ https://$http_host$request_uri? redirect;
try_files $uri $uri/ =404;
}
location /upload/ {
alias /var/www/html/upload/;
}
}

本地写一个bash脚本,当执行hl my_image.jpg的时候,会把图片自动上传到公开目录并将合成的url复制。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#!/bin/bash


md5=`md5 -q "$1"`
filename=$(basename -- "$1")
extension="${filename##*.}"

hashedName="$md5.$extension"

echo "file name is : $hashedName"

# cp $1 /tmp/$hashedName

scp "$1" gyorou@bocchi.tokyo:/var/www/html/upload/$hashedName

if [ $? -eq 0 ]; then
echo "https://www.bocchi.tokyo/upload/$hashedName" | pbcopy
echo "copied https://www.bocchi.tokyo/upload/$hashedName to clipboard"
else
echo FAIL
fi

当然为了在上传过程中不提示输入密码,ssh的无密码登陆也需要设置好。不过这个就略去不谈了。

试一下效果。

后记

看了一下现在服务器的容量,大概暂时是没有什么问题。
接下来可能会考虑把博客和邮箱完全扔到NAS上,彻底省去服务器的这笔开销吧。

3-sum-closest

问题

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
[15] 3Sum  

https://leetcode.com/problems/3sum/description/

* algorithms
* Medium (24.60%)
* Total Accepted: 631K
* Total Submissions: 2.6M
* Testcase Example: '[-1,0,1,2,-1,-4]'

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:


Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解析

和3-sum问题不一样的是,这次要寻找的不是三个数只和为0,而是最接近target的三个元素之和。

但是思路还是共通的。我们首先对nums进行排序,然后遍历排序好的数组sorted。

对于每个数组的元素sorted[i], 我们初始化左边界left为i+1,右边界为right-1。然后根据 sorted[i] + sorted[left] + sorted[right]和target的比较结果去移动边界。

我们初始化最小差距 min= sorted[0] + sorted[1] + sorted[2] - target

每当sorted[i] + sorted[left] + sorted[right] - target的绝对值小于min的绝对值,我们更新min。

每当sorted[i] + sorted[left] + sorted[right] - target > 0 说明三个数只和太大了,我们移动右边界减少三个数之和。

每当sorted[i] + sorted[left] + sorted[right] - target < 0 说明三个数只和太小了,我们移动左边界增加三个数之和。

sorted[i] + sorted[left] + sorted[right] - target == 0 那最好,我们直接返回target

当遍历完最后一个元素,我们返回min + target

解法

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
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def three_sum_closest(nums, target)
sorted = nums.sort
i = 0
min = sorted[0] + sorted[1] + sorted[2] - target
while i < sorted.length - 2
if i > 0 && sorted[i] == sorted[i-1]
i+=1
next
end
left = i+1
right = sorted.length - 1
while (left < right)
if (sorted[left] + sorted[right] + sorted[i] - target).abs < min.abs
min = sorted[left] + sorted[right] + sorted[i] - target
end
if sorted[left] + sorted[right] + sorted[i] - target > 0
right -=1
elsif sorted[left] + sorted[right] + sorted[i] - target < 0
left +=1
else
return sorted[left] + sorted[right] + sorted[i]
end
if left + 1 < right && sorted[left] == sorted[left+1]
left+=1
next
end
if right - 1 > left && sorted[right] == sorted[right-1]
right-=1
next
end
end
i += 1
end
return min + target
end

puts three_sum_closest([-1,0,1,1,55], 3)

反思

还好这题在每看结果的情况下通过了。为了二刷还是mark一下吧。